MAGMA

gistfile1.cpp

class POLICE {
public:
	
	int dis[200], disp[5], nex[200], t_nex[200], ppos[5], ptic[5];
	vector<int> xkoh[25];
	bool used[200];
	
	
	vector<int> POLICE_AI (int N, int S, const vector<int> WAY[4][200], const vector<int>& START, int TURN, int X_POS, int X_USED_TICKET[25], const int P_POS[5], const int X_TICKET[5], const int P_TICKET[5][3]){
		const int INF = 10000000;
		vector<int> P, lis[5], tlis[5];
		bool bl;
		int tu = TURN, xpos, xtic, nexp;
		
		if(TURN == 1){
			nex[13] = 14; t_nex[13] = 1; nex[14] = 13; t_nex[14] = 1;
			nex[26] = 15; t_nex[26] = 0; nex[15] = 14; t_nex[15] = 0;
			nex[29] = 55; t_nex[29] = 1; nex[55] = 89; t_nex[55] = 1;
			nex[34] = 47; t_nex[34] = 0; nex[47] = 46; t_nex[47] = 0;
			nex[50] = 37; t_nex[50] = 0; nex[37] = 23; t_nex[37] = 0;
			nex[53] = 69; t_nex[53] = 0; nex[69] = 86; t_nex[69] = 0;
			nex[91] = 107; t_nex[91] = 0; nex[107] = 161; t_nex[107] = 1;
			nex[94] = 93; t_nex[94] = 0; nex[93] = 79; t_nex[93] = 2;
			nex[103] = 102; t_nex[103] = 0; nex[102] = 67; t_nex[102] = 1;
			nex[112] = 100; t_nex[112] = 0; nex[100] = 111; t_nex[100] = 1;
			nex[117] = 116; t_nex[117] = 0; nex[116] = 142; t_nex[116] = 1;
			nex[132] = 126; t_nex[132] = 0; nex[126] = 140; t_nex[126] = 0;
			nex[138] = 124; t_nex[138] = 0; nex[124] = 153; t_nex[124] = 1;
			nex[141] = 133; t_nex[141] = 0; nex[133] = 157; t_nex[133] = 1;
			nex[155] = 154; t_nex[155] = 0; nex[154] = 153; t_nex[154] = 1;
			nex[174] = 161; t_nex[174] = 0; nex[161] = 128; t_nex[161] = 1;
			nex[197] = 184; t_nex[197] = 0; nex[184] = 153; t_nex[184] = 1;
			nex[198] = 187; t_nex[198] = 0; nex[187] = 185; t_nex[187] = 1;
		}
		
		for(int i = 0; i < 5; i++){
			ppos[i] = P_POS[i];
			if(APPEAR_TURN[i] >= TURN) tu = min(tu,APPEAR_TURN[i] - TURN);	
		}
		
		
		if(TURN < 3){
			for(int i = 0; i < 5; i++){
				bl = true;
				for(int j = 0; j < 5; j++){
					if(ppos[j] == nex[ppos[i]]) bl = false;
				}
				
				if(bl){
					ptic[i] = t_nex[ppos[i]];
					ppos[i] = nex[ppos[i]];
				} else {
					for(int h = 2; h >= 0; h--){
						for(int j = 0; j < WAY[h][ppos[i]].size(); j++){
							bl = true;
							for(int k = 0; k < 5; k++){
								if(ppos[k] == WAY[h][ppos[i]][j]) bl = false;
							}
							if(bl) lis[i].push_back(WAY[h][ppos[i]][j]);
						}
						
						if(lis[i].size()){
							ppos[i] = lis[i][rand()%lis[i].size()];
							ptic[i] = h;
							break;
						}
					}
				}
			}
			
			for(int i = 0; i < 5; i++){P.push_back(ppos[i]); P.push_back(ptic[i]);}
			return P;
		}
		
		
		if(tu == 0){
			xkoh[TURN].push_back(X_POS);
		} else {
			for(int i = 0; i < 200; i++) used[i] = false;
			
			for(int i = 0; i < xkoh[TURN-1].size(); i++){
				xpos = xkoh[TURN-1][i]; xtic = X_USED_TICKET[TURN];
				
				bl = false;
				for(int k = 0; k < 5; k++){
					if(ppos[k] == xpos) bl = true;
				}
				if(bl) continue;
				
				if(xtic == 3){
					for(int k = 0; k < 4; k++) for(int j = 0; j < WAY[k][xpos].size(); j++){
						nexp = WAY[k][xpos][j];
						if(used[nexp]) continue;
						used[nexp] = true;
						bl = true;
						for(int h = 0; h < 5; h++){
							if(ppos[h] == nexp) bl = false;
						}
						if(bl) xkoh[TURN].push_back(nexp);
					}
				} else {
					for(int j = 0; j < WAY[xtic][xpos].size(); j++) {
						nexp = WAY[xtic][xpos][j];
						if(used[nexp]) continue;
						used[nexp] = true;
						bl = true;
						for(int h = 0; h < 5; h++){
							if(ppos[h] == nexp) bl = false;
						}
						if(bl) xkoh[TURN].push_back(nexp);
					}
				}
			}
		}
		
		
		for(int i = 0; i < 200; i++) dis[i] = INF;
		queue<int> q;
		for(int i = 0; i < xkoh[TURN].size(); i++){
			dis[xkoh[TURN][i]] = 0;
			q.push(xkoh[TURN][i]);
		}
		
		while(!q.empty()){
			int v = q.front(); q.pop();
			for(int i = 0; i < 3; i++){
				for(int j = 0; j < WAY[i][v].size(); j++){
					if(dis[WAY[i][v][j]] == INF){
						dis[WAY[i][v][j]] = dis[v]+1;
						q.push(WAY[i][v][j]);
					}
				}
			}
		}
		
		for(int i = 0; i < 5; i++){
			int sdis = INF;
			for(int k = 0; k < 3; k++){
				if(!P_TICKET[i][k]) continue;
				for(int j = 0; j < WAY[k][ppos[i]].size(); j++){
					bl = true;
					xpos = WAY[k][ppos[i]][j];
					for(int h = 0; h < 5; h++){
						if(ppos[h] == xpos) bl = false;
					}
					if(bl && sdis >= dis[xpos]){
						if(sdis > dis[xpos]){lis[i].clear(); tlis[i].clear(); sdis = dis[xpos];}
						lis[i].push_back(xpos);
						tlis[i].push_back(k);
					}
				}
			}
			
			if(lis[i].size()){
				int rnd = rand() % lis[i].size();
				ppos[i] = lis[i][rnd];
				ptic[i] = tlis[i][rnd];
			} else {
				for(int k = 0; k < 3; k++){
					if(!P_TICKET[i][k]) continue;
					for(int j = 0; j < WAY[k][ppos[i]].size(); j++){
						bl = true;
						xpos = WAY[k][ppos[i]][j];
						for(int h = 0; h < 5; h++){
							if(ppos[h] == xpos) bl = false;
						}
						if(bl){
							lis[i].push_back(xpos);
							tlis[i].push_back(k);
						}
					}
				}
				
				if(lis[i].size()){
					int rnd = rand() % lis[i].size();
					ppos[i] = lis[i][rnd];
					ptic[i] = tlis[i][rnd];
				} else {
					ptic[i] = -1;
				}
			}
		}
		
		
		for(int i = 0; i < 5; i++){
			if(ptic[i] == -1){
				P.push_back(-1);
				P.push_back(-1);
			} else {
				P.push_back(ppos[i]);
				P.push_back(ptic[i]);
			}
		}
		return P;
	}
	
};