Submission #1380448
Source Code Expand
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<map>
#include<functional>
#include<chrono>
#include<random>
#include<cmath>
using namespace std;
using namespace chrono;
typedef long long int llint;
typedef bool izryt;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
const int big=1e9;//Multipleの評価関数
const int n=50;
const int k=8;
const int timepas=64;
const double npowda[10]={15,10,6,4,3.2,2.8,2.2,1.8,1.5,1.2};
const double quegen[10]={0,0.5,0.5,0.5,0.5,1,1.5,2.5,3.5,10};
const int STime=990;//上書きありサーチタイム/10
decltype(chrono::system_clock::now()) starttime;
std::random_device seed_gen;
mt19937 engine(seed_gen());
vector<vector<int>>grd;
vector<vector<int>>used;//どれにつかわれたかな
class pOint{
public:int x,y;
int grpot(void)const{return grd[y][x];}
bool operator ==(const pOint&obj)const{return this->x==obj.x&&this->y==obj.y;}
bool operator <(const pOint&obj)const{
if(this->grpot()==obj.grpot()){return rand()%2;}
return this->grpot()<obj.grpot();
}
};
pOint mpo(int ix,int iy){//make_pointみたいな
pOint Po;
Po.x=ix;
Po.y=iy;
return Po;
}
class pease{public:int sc;pOint mas[8];};
int getmytime(){
static int timecount=timepas-1;
static int maehaka=0;
timecount++;
if(timecount==timepas){
timecount=0;
auto nowtime=system_clock::now();
milliseconds ret=duration_cast<milliseconds>(nowtime-starttime);
return ret.count();
}else{
return maehaka;
}
}
vector<pease>peses;//どれがどれを持っているか,sc==0ならそのピースは存在しない
int main(void){
std::uint32_t seed = std::random_device()();
engine.seed(seed);
bool debug=false;
int h,i,j,k,gen;
cin>>h>>i>>j;//いらん
if(j==9){debug=true;}
pease Pe;Pe.sc=0;
grd.res(n);used.res(n);
for(i=0;i<8;i++){Pe.mas[i].x=0;Pe.mas[i].y=0;}
for(i=0;i<n;i++){grd[i].res(n);used[i].res(n);}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
char c;cin>>c;grd[i][j]=c-48;
}
}
starttime=system_clock::now();
peses.pub(Pe);//晩兵
while(getmytime()<STime*10-100){
if(debug){cout<<"wrre"<<endl;}
int X=engine()%50;
int Y=engine()%50;
double pownum=npowda[getmytime()/STime];
priority_queue<pair<double,pOint>> que;
vector<pOint> mot;
que.push(mp(grd[Y][X],mpo(X,Y)));
while(mot.size()<8&&(!que.empty())){
X=que.top().sec.x;
Y=que.top().sec.y;
if(que.top().fir<=0){break;}
if(mot.size()>0&&find(mot.begin(),mot.end(),mpo(X,Y))!=mot.end()){que.pop();continue;}
mot.pub(que.top().sec);
que.pop();
int gens=0;
if(used[Y+1][X]!=0){gens=quegen[getmytime()/STime];}
if(Y+1<n){que.push(mp(grd[Y+1][X]-gens,mpo(X,Y+1)));}
if(used[Y-1][X]!=0){gens=quegen[getmytime()/STime];}
if(Y>0){que.push(mp(grd[Y-1][X]-gens,mpo(X,Y-1)));}
if(used[Y][X+1]!=0){gens=quegen[getmytime()/STime];}
if(X+1<n){que.push(mp(grd[Y][X+1]-gens,mpo(X+1,Y)));}
if(used[Y][X-1]!=0){gens=quegen[getmytime()/STime];}
if(X>0){que.push(mp(grd[Y][X-1]-gens,mpo(X-1,Y)));}
//cout<<"bag"<<endl;
}
if(mot.size()<8){continue;}
double nowpot=0,genpot=1;
for(i=0;i<8;i++){genpot*=mot[i].grpot();Pe.mas[i]=mot[i];}
Pe.sc=genpot;
nowpot+=pow(genpot,pownum);
//npot乗のWAで判定する
vector<int>had;//判定済みか
for(i=0;i<8;i++){
if(used[mot[i].y][mot[i].x]!=0){
if(find(had.begin(),had.end(),used[mot[i].y][mot[i].x])!=had.end()){continue;}
nowpot-=pow(peses[used[mot[i].y][mot[i].x]].sc,pownum);
had.pub(used[mot[i].y][mot[i].x]);
}
}
if(debug){cout<<"de "<<nowpot<<endl;}
if(nowpot<=0){continue;}
for(i=0;i<had.size();i++){
peses[had[i]].sc=0;
if(debug){cout<<"i="<<had[i]<<endl;}
for(j=0;j<8;j++){
if(debug){cout<<" peseiti"<<peses[had[i]].mas[j].y<<" "<<peses[had[i]].mas[j].x<<endl;}
used[peses[had[i]].mas[j].y][peses[had[i]].mas[j].x]=0;
}
}
peses.pub(Pe);
if(debug){cout<<peses.size()<<endl;}
for(j=0;j<8;j++){used[mot[j].y][mot[j].x]=peses.size()-1;}
if(debug){cout<<"ok"<<endl;}
}
if(debug){cout<<"w"<<endl;}
int Ccount=0;
for(i=1;i<peses.size();i++){
if(peses[i].sc!=0){Ccount++;}
}
cout<<Ccount<<endl;
for(i=1;i<peses.size();i++){
if(peses[i].sc==0){continue;}
for(j=0;j<8;j++){cout<<peses[i].mas[j].y+1<<" "<<peses[i].mas[j].x+1<<endl;}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
WA_TLE |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
4800 Byte |
Status |
RE |
Exec Time |
97 ms |
Memory |
384 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
RE |
97 ms |
384 KB |
subtask_01_02.txt |
RE |
97 ms |
256 KB |
subtask_01_03.txt |
RE |
97 ms |
256 KB |
subtask_01_04.txt |
RE |
97 ms |
256 KB |
subtask_01_05.txt |
RE |
95 ms |
256 KB |
subtask_01_06.txt |
RE |
96 ms |
256 KB |
subtask_01_07.txt |
RE |
95 ms |
256 KB |
subtask_01_08.txt |
RE |
96 ms |
256 KB |
subtask_01_09.txt |
RE |
96 ms |
256 KB |
subtask_01_10.txt |
RE |
96 ms |
256 KB |