Submission #1370600


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=100;//一つつなげると得点
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=30;
const int loopnum=2000;
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+engine()%5-2;
		int ol=oline+engine()%5-2;
		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;
			}
			//cout<<"re";
		}
		//cout<<"w";
		//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])<<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;
		
	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 3749
Code Size 5312 Byte
Status AC
Exec Time 1110 ms
Memory 256 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 445 / 2500 265 / 2500 298 / 2500 484 / 2500 423 / 2500 425 / 2500 234 / 2500 468 / 2500 385 / 2500 322 / 2500
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 1097 ms 256 KB
subtask_01_02.txt AC 933 ms 256 KB
subtask_01_03.txt AC 1008 ms 256 KB
subtask_01_04.txt AC 1068 ms 256 KB
subtask_01_05.txt AC 1110 ms 256 KB
subtask_01_06.txt AC 1083 ms 256 KB
subtask_01_07.txt AC 1014 ms 256 KB
subtask_01_08.txt AC 1061 ms 256 KB
subtask_01_09.txt AC 1068 ms 256 KB
subtask_01_10.txt AC 1086 ms 256 KB