gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long ll;
static const int MOD = 0x7fffffff;
static const int MUL = 48271;
static const int DR[]={-1,0,1,0};
static const int DC[]={0,1,0,-1};
static const int boardSize=16*16;
static const int learchPoint=45;
static const int chainPoint1=3;
static const int chainPoint2=5;
static const int scoreShift=6;
static const int searchBuf[]={
	44,//0
	44,//1
	44,//2
	44,//3
	44,//4
	44,//5
	44,//6
	44,//7
	44,//8
	44,//9
	33,//10
	22,//11
	13,//12
	10,//13
	7,//14
	6,//15
	5 //16
};

int colors,n;
vector<string> board;
int seed;
vector<int> ret(30000);
char sq22[20000][2][2];
char bo[16][16];

int getNextColor(){
	int res=(seed%colors);
	seed=((ll)seed*MUL)%MOD;
	return res;
}

class state{
public:
	char bo[16][16];
	char us[16][16];
	int score,value,colorValue,learchValue;
	char x,y,d,sxs,sxe,sys,sye;
	char prevSwapColor1,prevSwapColor2;
	state(char bo_[16][16]){
		memcpy(bo,bo_,boardSize);
		score=0;
		searchInit();
	}
	state(const state* s){
		memcpy(bo,s->bo,boardSize);
		memcpy(us,s->us,boardSize);
		score=s->score;
		colorValue=s->colorValue;
		learchValue=s->learchValue;
		x=s->x;
		y=s->y;
		d=s->d;
	}
	inline bool checkSwap(int x,int y,int d){
		char color1=bo[x][y],color2=bo[x+DR[d]][y+DC[d]];
		return color1!=color2 && (prevSwapColor1==-1 || 
			prevSwapColor1==color1 || prevSwapColor1==color2 || prevSwapColor2==color1 || prevSwapColor2==color2);
	}
	inline void searchInit(){
		sxs=sys=0;
		sxe=sye=n;
		prevSwapColor1=-1;
	}
	inline state step(int x,int y,int d){
		state next(this);
		next.stepCalc(x,y,d);
		return next;
	}
	inline void swap(int x1,int y1,int x2,int y2){
		char c=bo[x1][y1];
		bo[x1][y1]=bo[x2][y2];
		bo[x2][y2]=c;
	}
	inline int chainExpectation(int x,int y){
		int res=0;
		if(x>0 && bo[x-1][y]==bo[x-1][y+1] && us[x-1][y]==3)res+=chainPoint1;
		if(x+2<n && bo[x+2][y]==bo[x+2][y+1] && us[x+2][y]==3)res+=chainPoint1;
		if(y>0 && bo[x][y-1]==bo[x+1][y-1] && us[x][y-1]==3)res+=chainPoint1;
		if(y+2<n && bo[x][y+2]==bo[x+1][y+2] && us[x][y+2]==3)res+=chainPoint1;
		if(x>0 && y>0 && bo[x-1][y-1]==bo[x][y-1] && bo[x-1][y-1]==bo[x-1][y])res+=chainPoint2;
		if(x>0 && y+2<n && bo[x-1][y+2]==bo[x-1][y+1] && bo[x-1][y+2]==bo[x][y+2])res+=chainPoint2;
		if(x+2<n && y>0 && bo[x+2][y-1]==bo[x+1][y-1] && bo[x+2][y-1]==bo[x+2][y])res+=chainPoint2;
		if(x+2<n && y+2<n && bo[x+2][y+2]==bo[x+1][y+2] && bo[x+2][y+2]==bo[x+2][y+1])res+=chainPoint2;
		return res;
	}
	inline int colorExpectation(int x,int y){
		int res=0,color=bo[x][y];
		if(x>0 && y>0 && color==bo[x-1][y-1])res++;
		if(x>0 && color==bo[x-1][y])res+=2;
		if(x>0 && y+1<n && color==bo[x-1][y+1])res++;
		if(y>0 && color==bo[x][y-1])res+=2;
		if(y+1<n && color==bo[x][y+1])res+=2;
		if(x+1<n && y>0 && color==bo[x+1][y-1])res++;
		if(x+1<n && color==bo[x+1][y])res+=2;
		if(x+1<n && y+1<n && color==bo[x+1][y+1])res++;
		return res;
	}
	void stepCalc(int x,int y,int d){
		int xs=0,xe=n,ys=0,ye=n;
		bool ok=false;
		{// swap
			if(d!=-1){
				int x1=x+DR[d],y1=y+DC[d];
				colorValue-=colorExpectation(x,y)+colorExpectation(x1,y1);
				prevSwapColor1=bo[x][y];
				prevSwapColor2=bo[x1][y1];
				bo[x][y]=prevSwapColor2;
				bo[x1][y1]=prevSwapColor1;
				colorValue+=colorExpectation(x,y)+colorExpectation(x1,y1);
				if((us[x][y]!=3 && us[x][y]!=2) || (us[x1][y1]!=3 && us[x1][y1]!=2)){
					us[x][y]=us[x1][y1]=3;
					ok=true;
				}
				xs=max(0,x-1);
				xe=min(n,x1+1);
				ys=max(0,y-1);
				ye=min(n,y1+1);

				sxs=max(0,x-2);
				sxe=min(n,x1+2);
				sys=max(0,y-2);
				sye=min(n,y1+2);
			}
		}
		bool firstRemove=true;
		{// removeSquares
			restart:
			for(int x=xs;x<xe;++x){
				for(int y=ys;y<ye;++y){
					if(x+1<n && y+1<n && bo[x][y]==bo[x+1][y] && bo[x][y]==bo[x][y+1] && bo[x][y]==bo[x+1][y+1]){
						ok=false;
						colorValue-=colorExpectation(x,y)+colorExpectation(x+1,y)+colorExpectation(x,y+1)+colorExpectation(x+1,y+1);
						if(firstRemove){
							learchValue-=learchPoint+chainExpectation(x,y);
							firstRemove=false;
						}
						bo[x][y]=sq22[score][0][0];
						bo[x+1][y]=sq22[score][1][0];
						bo[x][y+1]=sq22[score][0][1];
						bo[x+1][y+1]=sq22[score][1][1];
						colorValue+=colorExpectation(x,y)+colorExpectation(x+1,y)+colorExpectation(x,y+1)+colorExpectation(x+1,y+1);
						us[x][y]=us[x+1][y]=us[x][y+1]=us[x+1][y+1]=3;
						xs=min(xs,max(0,x-1));
						xe=max(xe,min(n-1,x+2));
						ys=min(ys,max(0,y-1));
						ye=max(ye,min(n-1,y+2));
						searchInit();
						score++;
						goto restart;
					}
				}
			}
			if(ok){
				value=0;
				return;
			}
		}
		calcValue(max(0,xs-2),min(n,xe+3),max(0,ys-2),min(n,ye+3));
	}
	inline void calcAllValue(){
		colorValue=learchValue=0;
		memset(us,3,sizeof(us));
		calcValue(0,n,0,n);
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j){
				if(us[i][j]==3){
					colorValue+=colorExpectation(i,j);
				}
			}
		}
		value=(score<<scoreShift)+colorValue+learchValue;
	}
	inline void calcValue(int xs,int xe,int ys,int ye){
		for(int i=xs;i<xe;++i){
			for(int j=ys;j<ye;++j){
				int color=bo[i][j];
				if(us[i][j]!=3)continue;
				if(i+1<n && color==bo[i+1][j] && us[i+1][j]==3){
					if(j>1){
						if(color==bo[i][j-1] && color==bo[i+1][j-2] && us[i][j-1]==3 && us[i+1][j-2]&2 && us[i+1][j-1]&1){
							swap(i+1,j-1,i+1,j-2);
							learchValue+=learchPoint+chainExpectation(i,j-1);
							swap(i+1,j-1,i+1,j-2);
							us[i][j]=us[i+1][j]=us[i][j-1]=0;
							us[i+1][j-2]&=1;
							us[i+1][j-1]&=2;
							continue;
						}else if(color==bo[i+1][j-1] && color==bo[i][j-2] && us[i+1][j-1]==3 && us[i][j-2]&2 && us[i][j-1]&1){
							swap(i,j-1,i,j-2);
							learchValue+=learchPoint+chainExpectation(i,j-1);
							swap(i,j-1,i,j-2);
							us[i][j]=us[i+1][j]=us[i+1][j-1]=0;
							us[i][j-2]&=1;
							us[i][j-1]&=2;
							continue;
						}
					}
					if(j+2<n){
						if(color==bo[i][j+1] && color==bo[i+1][j+2] && us[i][j+1]==3 && us[i+1][j+2]&2 && us[i+1][j+1]&1){
							swap(i+1,j+1,i+1,j+2);
							learchValue+=learchPoint+chainExpectation(i,j);
							swap(i+1,j+1,i+1,j+2);
							us[i][j]=us[i+1][j]=us[i][j+1]=0;
							us[i+1][j+2]&=1;
							us[i+1][j+1]&=2;
							continue;
						}else if(color==bo[i+1][j+1] && color==bo[i][j+2] && us[i+1][j+1]==3 && us[i][j+2]&2 && us[i][j+1]&1){
							swap(i,j+1,i,j+2);
							learchValue+=learchPoint+chainExpectation(i,j);
							swap(i,j+1,i,j+2);
							us[i][j]=us[i+1][j]=us[i+1][j+1]=0;
							us[i][j+2]&=1;
							us[i][j+1]&=2;
							continue;
						}
					}
				}
				if(j+1<n && color==bo[i][j+1] && us[i][j+1]==3){
					if(i>1){
						if(color==bo[i-1][j] && color==bo[i-2][j+1] && us[i-1][j]==3 && us[i-2][j+1]&2 && us[i-1][j+1]&1){
							swap(i-1,j+1,i-2,j+1);
							learchValue+=learchPoint+chainExpectation(i-1,j);
							swap(i-1,j+1,i-2,j+1);
							us[i][j]=us[i][j+1]=us[i-1][j]=0;
							us[i-2][j+1]&=1;
							us[i-1][j+1]&=2;
							continue;
						}else if(color==bo[i-1][j+1] && color==bo[i-2][j] && us[i-1][j+1]==3 && us[i-2][j]&2 && us[i-1][j]&1){
							swap(i-1,j,i-2,j);
							learchValue+=learchPoint+chainExpectation(i-1,j);
							swap(i-1,j,i-2,j);
							us[i][j]=us[i][j+1]=us[i-1][j+1]=0;
							us[i-2][j]&=1;
							us[i-1][j]&=2;
							continue;
						}
					}
					if(i+2<n){
						if(color==bo[i+1][j] && color==bo[i+2][j+1] && us[i+1][j]==3 && us[i+2][j+1]&2 && us[i+1][j+1]&1){
							swap(i+1,j+1,i+2,j+1);
							learchValue+=learchPoint+chainExpectation(i,j);
							swap(i+1,j+1,i+2,j+1);
							us[i][j]=us[i][j+1]=us[i+1][j]=0;
							us[i+2][j+1]&=1;
							us[i+1][j+1]&=2;
							continue;
						}else if(color==bo[i+1][j+1] && color==bo[i+2][j] && us[i+1][j+1]==3 && us[i+2][j]&2 && us[i+1][j]&1){
							swap(i+1,j,i+2,j);
							learchValue+=learchPoint+chainExpectation(i,j);
							swap(i+1,j,i+2,j);
							us[i][j]=us[i][j+1]=us[i+1][j+1]=0;
							us[i+2][j]&=1;
							us[i+1][j]&=2;
							continue;
						}
					}
				}
			}
		}
		value=(score<<scoreShift)+colorValue+learchValue;
	}
};

class compare{
public:
	bool operator() (const state& s1,const state& s2) {
		return s1.value<s2.value;
	}
};

class SquareRemover{
public:
	vector<int> playIt(int colors_,vector<string> board_,int seed_){
		{// init
			colors=colors_;
			board=board_;
			seed=seed_;
			n=board.size();
			for(int i=0;i<20000;++i){
				sq22[i][0][0]=getNextColor();
				sq22[i][0][1]=getNextColor();
				sq22[i][1][0]=getNextColor();
				sq22[i][1][1]=getNextColor();
			}
			for(int i=0;i<n;++i){
				for(int j=0;j<n;++j){
					bo[i][j]=board[i][j]-'0';
				}
			}
		}
		int searchState=searchBuf[n];
		state now(bo);
		now.stepCalc(0,0,-1);
		now.searchInit();
		int witch=20;
		for(int i=0;i<10000;++i){
			priority_queue<state,vector<state>,compare> pq[4];
			int depth=0;
			now.calcAllValue();
			now.searchInit();
			pq[0].push(now);
			int value=0,nextX=-1,nextY=-1,nextD=-1;
			for(int search=0,w=0;search<searchState;search++,w++){
				if(pq[depth].empty() || w>=witch){
					w=0;
					depth++;
				}
				state st=pq[depth].top();pq[depth].pop();
				//cerr<<depth<<" "<<st.value<<" "<<pq[depth].size()<<endl;
				for(int x=st.sxs,xend=st.sxe;x<xend;++x){
					for(int y=st.sys,yend=st.sye;y<yend;++y){
						if(y+1<n && st.checkSwap(x,y,1)){
							state tmpState=st.step(x,y,1);
							if(depth==0){
								tmpState.x=x;
								tmpState.y=y;
								tmpState.d=1;
							}
							pq[depth+1].push(tmpState);
							if(tmpState.value>value){
								value=tmpState.value;
								nextX=tmpState.x;
								nextY=tmpState.y;
								nextD=tmpState.d;
							}
						}
						if(x+1<n && st.checkSwap(x,y,2)){
							state tmpState=st.step(x,y,2);
							if(depth==0){
								tmpState.x=x;
								tmpState.y=y;
								tmpState.d=2;
							}
							pq[depth+1].push(tmpState);
							if(tmpState.value>value){
								value=tmpState.value;
								nextX=tmpState.x;
								nextY=tmpState.y;
								nextD=tmpState.d;
							}
						}
					}
				}
			}
			now.stepCalc(nextX,nextY,nextD);
			ret[i*3]=nextX;
			ret[i*3+1]=nextY;
			ret[i*3+2]=nextD;
		}
		cerr<<"score: "<<now.score<<endl;
		return ret;
	}
};

int main() {
	cin>>colors>>n;
	for(int i=0;i<n;++i){
		string s;
		cin>>s;
		board.push_back(s);
	}
	cin>>seed;

	SquareRemover test;
	vector<int> ret = test.playIt(colors,board,seed);

	for(int i=0;i<30000;++i){
		cout<<ret[i]<<endl;
	}
	cout<<flush<<endl;
}