Submission #1370645
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=17;
const int n=50;
const int renp=30;//一つつなげると得点
const int bra=20;//両方バランスよく残すと高得点
const int brn[10]={0,25,20,16,12,10,8,6,5,4};//×どうしがつながってないと得点
const int ran=30;
const int hava=50;
const int loopnum=800;
const int pas=50;
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;
}
pair<int,int> hantei(const string& befcol,string& kou){
int ans=0;
int i,j,ok=0,xk=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;}//つながってないのでダメ
xk++;
for(j=i;j>0;j--){
if(kou[j-1]=='v'){kou[j-1]='x';xk++;}//復活チャンス
else{break;}
}
for(j=i-1;j>0&&kou[j-1]!='x'&&i-j<10;j--){
ans+=brn[i-j];
}
}
for(i=0;i<kou.size();i++){
if(kou[i]!='o'){continue;}
if(befcol[i]!='o'&&(i==0||kou[i-1]!='o')){kou[i]='p';continue;}//つながってないのでダメ
ok++;
for(j=i;j>0;j--){
if(kou[j-1]=='p'){kou[j-1]='o';ok++;}//復活チャンス
else{break;}
}
for(j=i-1;j>0&&kou[j-1]!='o'&&i-j<10;j--){
ans+=brn[i-j];
}
}
ans+=engine()%ran+engine()%ran;
ans+=(ok+xk)*renp;
ans+=(ok*xk)*bra;
return mp(ans,ok+xk);
}
int main(void){
starttime=system_clock::now();
std::uint32_t seed = std::random_device()();
engine.seed(seed);
bool debug=false;
int h,i,j,k,gen;
vector<string>mat(n);//mat[横の行][高さ]でアクセスする。
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<n;j++){
mat[j][i]=str[j];
}
if(str.size()>n){debug=true;}
}
//cout<<"q";
priority_queue<tuple<int,int,string,vector<string>>,
vector<tuple<int,int,string,vector<string>>>,
greater<tuple<int,int,string,vector<string>>>
>nowcol;//今の落下後のものを記録
//少ない順に出てくるので多いものが残る
//これのtop()と比較してより得点が高いならpush&pop
//現在評価,連結数,最後の落ちた後,答えの探索
vector<tuple<int,int,string,vector<string>>> befcol(hava);//前の落下後の行を記録
vector<string> vs;
str.res(n);
for(i=0;i<n;i++){str[i]='+';}
for(h=0;h<hava;h++){
int xl=xline;
int ol=oline;
str[xl]='x';
str[ol]='o';
befcol[h]=mt(0,0,str,vs);
str[xl]='+';
str[ol]='+';
}
//cout<<"we";
for(i=0;i<n;i++){
//cout<<"qdxf";
//int dot=0;
//for(j=0;j<n;j++){if(mat[i][j]=='.'){dot++;}}
for(int kai=0;kai<loopnum;kai++){
unsigned int bit=engine();
int nowdo=0;
string kou=mat[i];
for(j=0;j<n;j++){
if(kou[j]!='.'){continue;}
if(bit&(1<<nowdo)){kou[j]='+';}
if(engine()%100>pas){nowdo++;}
if(nowdo>30){nowdo=0;bit=engine();}
}
string kore=kou;
kou=drop(move(kou));
//cout<<"da";
string motokou=kou;
for(j=0;j<hava;j++){
kou=motokou;
pair<int,int>p;
p=hantei(get<2>(befcol[j]),kou);
if(hava<=nowcol.size()&&get<0>(nowcol.top())>=get<1>(befcol[j])*renp+p.fir){continue;}
if(hava==nowcol.size()){nowcol.pop();}
vs.clear();
vs=get<3>(befcol[j]);
vs.push_back(kore);
nowcol.push(mt(get<1>(befcol[j])*renp+p.fir,get<1>(befcol[j])+p.sec,kou,vs));
break;
}
}
//if(debug){cout<<"de "<<maxpot<<endl;}
befcol.clear();
befcol.res(nowcol.size());
j=0;
while(!nowcol.empty()){
befcol[j]=move(nowcol.top());
nowcol.pop();j++;
}
//if(debug){cout<<"de"<<get<0>(befcol[hava-1])<<" "<<get<1>(befcol[hava-1])<<" "<<get<2>(befcol[hava-1])<<endl;}
}
//befcolのうちget<1>が最大を見つける
vector<string>ans;
int maxpot=0,thpot=0;
for(i=0;i<hava;i++){
if(maxpot<get<1>(befcol[i])){maxpot=get<1>(befcol[i]);thpot=i;}
}
ans=get<3>(befcol[thpot]);
for(i=n-1;i>=0;i--){
for(j=0;j<n;j++){
cout<<ans[j][i];
}
cout<<endl;
}
vector<string>go(n);
if(debug){
for(i=0;i<n;i++){go[i]=drop(ans[i]);}
for(i=0;i<n;i++){while(go[i].size()<n){go[i].pub('*');}}
cout<<endl;cout<<get<1>(befcol[thpot])<<endl;cout<<endl;
int oxnum=0;
str.clear();str.res(n);
for(i=0;i<n;i++){str[i]='+';}
str[xline]='x';
str[oline]='o';
for(i=0;i<n;i++){
hantei(str,go[i]);
str=go[i];
}
for(i=0;i<n;i++){for(j=0;j<n;j++){if(ans[i][j]=='o'||go[i][j]=='x'){oxnum++;}}}
cout<<"oxnum="<<oxnum<<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 |
4228 |
Code Size |
5574 Byte |
Status |
AC |
Exec Time |
512 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 |
395 / 2500 |
422 / 2500 |
325 / 2500 |
483 / 2500 |
500 / 2500 |
392 / 2500 |
320 / 2500 |
423 / 2500 |
477 / 2500 |
491 / 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 |
482 ms |
384 KB |
subtask_01_02.txt |
AC |
486 ms |
384 KB |
subtask_01_03.txt |
AC |
478 ms |
384 KB |
subtask_01_04.txt |
AC |
496 ms |
384 KB |
subtask_01_05.txt |
AC |
512 ms |
384 KB |
subtask_01_06.txt |
AC |
510 ms |
384 KB |
subtask_01_07.txt |
AC |
497 ms |
384 KB |
subtask_01_08.txt |
AC |
503 ms |
384 KB |
subtask_01_09.txt |
AC |
498 ms |
384 KB |
subtask_01_10.txt |
AC |
506 ms |
384 KB |