TMCTF2015-prog400.cpp

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef __uint128_t uint128_t;
typedef pair<uint128_t, int > state_t;

template<typename T>
inline T sw(T x, int a, int b){
	T _a = ((x>>(4*a))&0xF);
	T _b = ((x>>(4*b))&0xF);
	return x-((_a)<<(4*a))-((_b)<<(4*b))+((_a)<<(4*b))+((_b)<<(4*a));
}

string solve(int len){
	char ms[100]="", mse[100]="";
	map<state_t, pair<int,int> > prev;
	map<state_t, pair<int,int> > next;
	
	queue<state_t> Q, QBack;
	vector<vector<int> > adj;
	for(int i=0;i<len;i++){
		adj.push_back(vector<int>());
		if(i>0) adj[i].push_back(len+i-1);
		adj[i].push_back(len+i);
		if(i<len-1) adj[i].push_back(len+i+1);
	}
	for(int i=0;i<len;i++){
		adj.push_back(vector<int>());
		if(i>0) adj[len+i].push_back(i-1);
		adj[len+i].push_back(i);
		if(i<len-1) adj[len+i].push_back(i+1);
	}
	
	uint128_t initial = 0;
	for(uint128_t i=0;i<len*2;i++) initial |= i<<(i*4);
	uint128_t target = sw(initial,0,len*2-1);
	
	prev[make_pair(initial,len*2-1)]=make_pair(-1,0);
	next[make_pair(target, 0)]=make_pair(-1,0);
	
	Q.push(make_pair(initial,2*len-1));
	QBack.push(make_pair(target, 0));
	
	bool found=false;
	state_t x_state;
	int lastQ = -1;
	int lastQBack = -1;
	//first stage: find minimum move
	while((Q.size()>0 || QBack.size()>0) && !found){
		while(Q.size()>0 && !found){
			state_t sn = Q.front();
			int qlen = prev[sn].second;
			if(qlen>lastQ) {lastQ++;break;}
			Q.pop();
			uint128_t s = sn.first;
			int c = sn.second;
			for(int j=0, je=adj[c].size();j<je;j++){
				int c2 = adj[c][j];
				uint128_t s2 = sw(s,c,c2);
				state_t new_state = make_pair(s2, c2);
				if(prev.find(new_state)==prev.end()){
					prev[new_state]=make_pair(c,qlen+1);
					Q.push(new_state);
					if(next.find(new_state)!=next.end()){
						if(!found) x_state = new_state;found=true;
					}
				}
			}
			lastQ = qlen;
		}
		while(!found && QBack.size()>0){
			state_t sn = QBack.front();
			int qlen = next[sn].second;
			if(qlen>lastQBack) {lastQBack++;break;}
			QBack.pop();
			uint128_t s = sn.first;
			int c = sn.second;
			for(int j=0, je=adj[c].size();j<je;j++){
				int c2 = adj[c][j];
				uint128_t s2 = sw(s,c,c2);
				state_t new_state = make_pair(s2, c2);
				if(next.find(new_state)==next.end()){
					next[new_state]=make_pair(c,qlen+1);
					QBack.push(new_state);
				}
			}
			lastQBack = qlen;
		}
	}
	string sol = "";
	//second, find the rest moves
	if(found){
		found = false;
		Q=queue<state_t>();
		Q.push(x_state);
		while(Q.size()>0 && !found){
			state_t sn = Q.front();
			int qlen = prev[sn].second;
			Q.pop();
			uint128_t s = sn.first;
			int c = sn.second;
			for(int j=0, je=adj[c].size();j<je;j++){
				int c2 = adj[c][j];
				uint128_t s2 = sw(s,c,c2);
				state_t new_state = make_pair(s2, c2);
				if(prev.find(new_state)==prev.end()){
					prev[new_state]=make_pair(c,qlen+1);
					Q.push(new_state);
					if(s2 == target){
						x_state = new_state;found=true;break;
					}
				}
			}
		}
		if(found){
			int mov = x_state.second;
			uint128_t state = x_state.first;
			while(mov>=0){
				sol.push_back('A'+mov);
				int new_mov = prev[make_pair(state, mov)].first;
				state = sw(state,mov,new_mov);
				mov=new_mov;
			}
			reverse(sol.begin(),sol.end());
			
			sol = sol.substr(1);
		} else sol="Uknown2";
	} else sol="Unknow1";
	return sol;
}

int main(int argc, char *argv[]) {
	for(int i=3;i<=8;i++)
		cout<<i<<" : TMCTF{"<<solve(i)<<"}"<<endl;
	return 0;
}