Submission #1370342
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> 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;//daikon3の評価関数 const int xline=7; const int oline=30; const int n=50; const int renp=100000;//一つつなげると得点 const int brop=10;//ブロックを残すと得点 const int uep=20;//連結されたブロックを上に積み上げると得点 const int brn=40;//×どうしがつながってないと得点 const int miru=25;//miruまでの.を消すかどうかで全探索 decltype(chrono::system_clock::now()) starttime; std::random_device seed_gen; mt19937 engine(seed_gen()); int gettime(){auto nowtime=system_clock::now(); milliseconds ret=duration_cast<milliseconds>(nowtime-starttime); return ret.count(); } string drop(string in){ string out; for(int i=0;i<n;i++){if(in[i]!='.'){out.pub(in[i]);}} return out; } int hantei(const string& befcol,string& kou){ int ans=0; int i,j,maxue=0; for(i=0;i<kou.size();i++){ if(kou[i]!='x'){continue;} if(befcol[i]!='x'&&(i==0||kou[i-1]!='x')){kou[i]='v';continue;}//つながってないのでダメ ans+=renp; maxue=i; for(j=i;j>0;j--){ if(kou[j-1]=='v'){kou[j-1]='x';ans+=renp;}//復活チャンス else{break;} } if(i>0&&kou[i-1]!='x'){ans+=brn;} } ans+=maxue*uep; return ans; } int main(void){ starttime=system_clock::now(); std::uint32_t seed = std::random_device()(); engine.seed(seed); int i,j,k,gen; vector<string>mat(n);//mat[横の行][高さ]でアクセスする。 vector<string>ans(n); for(i=0;i<n;i++){mat[i].res(n);} string str; for(i=n-1;i>=0;i--){ cin>>str; for(j=0;j<50;j++){ mat[j][i]=str[j]; } } ans=mat; string befcol;//前の落下後の行を記録 string nowcol; vector<string> go(n); for(i=0;i<xline;i++){befcol.pub('+');}befcol.pub('x'); for(i=xline+1;i<miru;i++){befcol.pub('+');} //cout<<hantei(befcol,drop(mat[0]))<<endl; for(i=0;i<n;i++){ int maxpot=0; int dot=0; for(j=0;j<miru;j++){if(mat[i][j]=='.'){dot++;}} for(int bit=0;bit<(1<<dot);bit++){ int nowdo=0; string kou=mat[i]; for(j=0;j<miru;j++){ if(kou[j]!='.'){continue;} if(bit&(1<<nowdo)){kou[j]='+';} nowdo++; } string kore=kou; kou=drop(move(kou)); int genpot=hantei(befcol,kou); if(maxpot<genpot){maxpot=genpot;ans[i]=kore;nowcol=kou;} } //cout<<"de "<<maxpot<<endl; befcol=nowcol; for(j=befcol.size();j<n;j++){befcol.pub('+');} go[i]=befcol; } //cout<<endl;cout<<endl;cout<<endl; for(i=n-1;i>=0;i--){ for(j=0;j<n;j++){ cout<<ans[j][i]; } cout<<endl; } /*cout<<endl;cout<<endl;cout<<endl; for(i=n-1;i>=0;i--){ for(j=0;j<n;j++){ cout<<go[j][i]; } cout<<endl; }*/ return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - ○×ブロック |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 2697 |
Code Size | 3381 Byte |
Status | AC |
Exec Time | 1416 ms |
Memory | 512 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 | 248 / 2500 | 193 / 2500 | 309 / 2500 | 194 / 2500 | 314 / 2500 | 296 / 2500 | 468 / 2500 | 223 / 2500 | 224 / 2500 | 228 / 2500 | ||||||||||||||||||||
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 | AC | 897 ms | 512 KB |
subtask_01_02.txt | AC | 803 ms | 256 KB |
subtask_01_03.txt | AC | 497 ms | 256 KB |
subtask_01_04.txt | AC | 1097 ms | 256 KB |
subtask_01_05.txt | AC | 559 ms | 256 KB |
subtask_01_06.txt | AC | 1416 ms | 256 KB |
subtask_01_07.txt | AC | 718 ms | 256 KB |
subtask_01_08.txt | AC | 1143 ms | 256 KB |
subtask_01_09.txt | AC | 677 ms | 256 KB |
subtask_01_10.txt | AC | 1262 ms | 256 KB |