MM98
// C++11 | |
#include <cstdlib> | |
#include <iostream> | |
#include <string> | |
#include <vector> | |
#include <string.h> | |
#include <random> | |
using namespace std; | |
#define rep(i,n) for(int i = 0; i < n; i++) | |
const unsigned long long int cycle_per_sec = 2500000000; | |
unsigned long long int getCycle() { | |
unsigned int low, high; | |
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); | |
return ((unsigned long long int)low) | ((unsigned long long int)high << 32); | |
} | |
double getTime (unsigned long long int begin_cycle) { | |
return (double)(getCycle() - begin_cycle) / cycle_per_sec; | |
} | |
class XorShift { | |
public: | |
unsigned int x; | |
unsigned int y; | |
unsigned int z; | |
unsigned int w; | |
unsigned int t; | |
XorShift(int tmp) { | |
mt19937 rnd(tmp); | |
x = rnd(); | |
y = rnd(); | |
z = rnd(); | |
w = rnd(); | |
t = 1; | |
} | |
int rand() { | |
t = x ^ (x << 11); | |
x = y; | |
y = z; | |
z = w; | |
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); | |
return w & 0x7fffffff; | |
} | |
} engine(rand()); | |
const int INF = 100000; | |
const int dy[5] = {-1, 0, 1, 0, 0}; | |
const int dx[5] = {0, 1, 0, -1, 0}; | |
const int mainG = 8; | |
const int MAX_S = 50; | |
const int MAX_K = 100; | |
const int MAX_P = 50; | |
const int MAX_M = 500; | |
const int MONTE_TIME1 = 5; | |
const int MONTE_TIME2 = 10; | |
const int rec_ex = 3; | |
XorShift best_engine(0); | |
class PrincessesAndMonsters { | |
public: | |
int corner[4][2]; //topleft, topright, bottomright, bottomleft | |
int rectangle[MAX_S][MAX_S]; | |
int rec_edge[4]; // top, right, bottom, left | |
int S; | |
int end_turn; | |
string dir_str = "NESWO"; | |
int split; | |
int G[2]; | |
int age[2]; | |
int rec_len[2]; | |
int rec_index[2]; // topleft, topright, bottomright, bottomleft | |
int rec_dir[2][2]; | |
bool age_first_day[2]; | |
int K[2]; | |
int Gindex[2][MAX_K]; | |
int Gsize[2]; | |
int Gknights[2][MAX_K*2]; | |
int Gdir[2][MAX_K]; | |
int knights[2][MAX_K*2]; | |
bool last_south[2]; | |
bool last_east[2]; | |
bool last_phase[2]; | |
int turn; | |
inline int distance (int &y, int &x, int &Y, int &X) { | |
return (x-X)*(x-X<0?-1:1)+(y-Y)*(y-Y<0?-1:1); | |
} | |
inline bool in_rectangle (int &y, int &x) { | |
return rec_edge[0] <= y && y <= rec_edge[2] && rec_edge[3] <= x && x <= rec_edge[1]; | |
} | |
inline bool in_board (int y, int x) { | |
return 0 <= y && y < S && 0 <= x && x < S; | |
} | |
void dynamic_init (vector<int> princesses, int ind, int KK, int _G, int pea) { | |
G[0] = _G; G[1] = _G; | |
if (ind == 0) { | |
K[0] = KK; | |
K[1] = 0; | |
} else { | |
K[0] = KK/2; | |
K[1] = KK-KK/2; | |
} | |
turn = 0; | |
age[0] = 0; age[1] = 0; | |
rec_edge[0] = S-1; rec_edge[1] = 0; rec_edge[2] = 0; rec_edge[3] = S-1; | |
for (int i = 0; i < princesses.size(); i += 2) { | |
rec_edge[0] = min(rec_edge[0], princesses[i]); | |
rec_edge[1] = max(rec_edge[1], princesses[i+1]); | |
rec_edge[2] = max(rec_edge[2], princesses[i]); | |
rec_edge[3] = min(rec_edge[3], princesses[i+1]); | |
} | |
rec_edge[0] = max(1, rec_edge[0]-rec_ex); | |
rec_edge[1] = min(S-2, rec_edge[1]+rec_ex); | |
rec_edge[2] = min(S-2, rec_edge[2]+rec_ex); | |
rec_edge[3] = max(1, rec_edge[3]-rec_ex); | |
//cerr << "hoge" << endl; | |
if (rec_edge[0] <= S-1-rec_edge[2]) { | |
if (S-1-rec_edge[1] <= rec_edge[3]) rec_index[0] = 1; | |
else rec_index[0] = 0; | |
} else { | |
if (S-1-rec_edge[1] <= rec_edge[3]) rec_index[0] = 2; | |
else rec_index[0] = 3; | |
} | |
rec_index[1] = (rec_index[0]+pea)%4; | |
rep(j,2) { | |
rep(i,K[j]) { | |
if (rec_index[j] <= 1) knights[j][2*i] = 0; | |
else knights[j][2*i] = S-1; | |
if (rec_index[j] == 1 || rec_index[j] == 2) knights[j][2*i+1] = S-1; | |
else knights[j][2*i+1] = 0; | |
} | |
if (rec_index[j] == 0) { | |
rec_dir[j][0] = 1; rec_dir[j][1] = 2; | |
} else if (rec_index[j] == 1) { | |
rec_dir[j][0] = 3; rec_dir[j][1] = 2; | |
} else if (rec_index[j] == 2) { | |
rec_dir[j][0] = 3; rec_dir[j][1] = 0; | |
} else { | |
rec_dir[j][0] = 1; rec_dir[j][1] = 0; | |
} | |
} | |
//cerr << "huga" << endl; | |
/* | |
rep(i,K[0]) cerr << knights[0][2*i] << " " << knights[0][2*i+1] << " "; | |
cerr << endl; | |
rep(i,K[1]) cerr << knights[1][2*i] << " " << knights[1][2*i+1] << " "; | |
cerr << endl; | |
*/ | |
//cerr << "?" << endl; | |
rep(i,2) rec_len[i] = 1+rec_edge[2]-rec_edge[0]+rec_edge[1]-rec_edge[3]; | |
memset(rectangle, 0, sizeof(rectangle)); | |
rep(i,2) { | |
last_south[i] = true; | |
last_east[i] = true; | |
last_phase[i] = false; | |
} | |
} | |
pair<int,int> battle (int x, int y) { | |
while (x != 0 && y != 0) { | |
if (engine.rand()%(x+y) < x) y--; | |
else x--; | |
} | |
return pair<int,int>(x,y); | |
} | |
// ---------------------------------------------- | |
string initialize (int SS, vector<int> princesses, vector<int> monsters, int KK) { | |
S = SS; | |
corner[0][0] = 0; corner[0][1] = 0; | |
corner[1][0] = 0; corner[1][1] = S-1; | |
corner[2][0] = S-1; corner[2][1] = S-1; | |
corner[3][0] = S-1; corner[3][1] = 0; | |
end_turn = S*S*S; | |
// --- | |
// G..[2,4], rec_ex..[0,5] | |
auto start = getCycle(); | |
int score[4][5]; | |
int monte = 0; | |
int board[3][MAX_S][MAX_S]; | |
int last_dead[3][MAX_S][MAX_S]; | |
bool dead[3][MAX_M]; | |
int follow[MAX_P]; | |
int now_princesses[MAX_P*2], now_monsters[MAX_M*2]; | |
int now_knights[MAX_K*2]; | |
int P = princesses.size()/2, M = monsters.size()/2; | |
int debug = 0; | |
//cerr << "ok" << endl; | |
vector<int> status; | |
memset(score, 0, sizeof(score)); | |
while (getTime(start) < MONTE_TIME1) { | |
//cerr << "monte" << endl; | |
monte++; | |
int xorrnd = engine.rand(); | |
for (int sp = 0; sp < 4; sp++) { | |
for (int _G = 1; _G <= 3; _G++) { | |
XorShift tmp_engine(xorrnd); | |
dynamic_init(princesses, (int)(sp!=0), KK, _G, sp); | |
//cerr << "dy init" << endl; | |
status = vector<int>(KK, 0); | |
memset(dead, 0, sizeof(dead)); | |
memset(follow, -1, sizeof(follow)); | |
int nowP = princesses.size()/2, nowM = monsters.size()/2; | |
for (int i = 0; i < 2*P; i++) now_princesses[i] = princesses[i]; | |
for (int i = 0; i < 2*M; i++) now_monsters[i] = monsters[i]; | |
//cerr << "ok1" << endl; | |
for (int _ = 0; _ < 5*S; _++) { | |
//cerr << "ok2" << endl; | |
memset(board, 0, sizeof(board)); | |
memset(last_dead, 0, sizeof(last_dead)); | |
int tmpP = 0; | |
int tmpK = 0; | |
for (int i = 0; i < status.size(); i++) { | |
if (status[i] > 0) tmpP += status[i]; | |
if (status[i] >= 0) tmpK++; | |
} | |
if (sp == 0) { | |
string tmp = split_move(status, nowP, nowM, INF, 0, tmpP, tmpK, engine); | |
} else { | |
string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), nowP, nowM, INF, 0, tmpP, tmpK, engine) | |
+ split_move(vector<int>(status.begin()+K[0], status.end()), nowP, nowM, INF, 1, tmpP, tmpK, engine); | |
} | |
if (sp == 0) { | |
for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i]; | |
} else { | |
for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i]; | |
for (int i = 0; i < 2*K[1]; i++) now_knights[2*K[0]+i] = knights[1][i]; | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
board[0][now_knights[i*2]][now_knights[i*2+1]]++; | |
} | |
//cerr << "ok3" << endl; | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
if (follow[i] != -1) { | |
now_princesses[2*i] = now_knights[2*follow[i]]; | |
now_princesses[2*i+1] = now_knights[2*follow[i]+1]; | |
} else { | |
int r; | |
while (true) { | |
r = tmp_engine.rand()%5; | |
if (in_board(now_princesses[2*i]+dy[r], now_princesses[2*i+1]+dx[r])) break; | |
} | |
now_princesses[2*i] += dy[r]; | |
now_princesses[2*i+1] += dx[r]; | |
} | |
if (now_princesses[2*i] == 0) { | |
if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) { | |
dead[1][i] = true; | |
nowP--; | |
} | |
} else if (now_princesses[2*i] == S-1) { | |
if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) { | |
dead[1][i] = true; | |
nowP--; | |
} | |
} | |
if (!dead[1][i]) board[1][now_princesses[2*i]][now_princesses[2*i+1]]++; | |
} | |
//cerr << "ok4" << endl; | |
for (int i = 0; i < M; i++) { | |
if (dead[2][i]) continue; | |
int r; | |
while (true) { | |
r = tmp_engine.rand()%5; | |
if (in_board(now_monsters[2*i]+dy[r], now_monsters[2*i+1]+dx[r])) break; | |
} | |
now_monsters[2*i] += dy[r]; | |
now_monsters[2*i+1] += dx[r]; | |
board[2][now_monsters[2*i]][now_monsters[2*i+1]]++; | |
} | |
/* | |
if (debug < 10) { | |
debug++; | |
for (int i = 0; i < 3; i++) { | |
for (int j = 0; j < S; j++) { | |
for (int k = 0; k < S; k++) { | |
cerr << board[i][j][k] << " "; | |
} | |
cerr << endl; | |
} | |
cerr << endl; | |
} | |
} | |
*/ | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
int cntK = board[0][y][x]; | |
int cntM = board[2][y][x]; | |
if (cntK == 0 || cntM == 0) continue; | |
pair<int,int> result = battle(cntK, cntM); | |
board[0][y][x] -= (cntK-result.first); | |
last_dead[0][y][x] = cntK-result.first; | |
board[2][y][x] -= (cntM-result.second); | |
last_dead[2][y][x] = cntM-result.second; | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
if (last_dead[0][y][x] > 0) { | |
dead[0][i] = true; | |
last_dead[0][y][x]--; | |
status[i] = -1; | |
} | |
} | |
//cerr << "ok5" << endl; | |
for (int i = 0; i < M; i++) { | |
if (dead[2][i]) continue; | |
int y = now_monsters[2*i], x = now_monsters[2*i+1]; | |
if (last_dead[2][y][x] > 0) { | |
dead[2][i] = true; | |
last_dead[2][y][x]--; | |
nowM--; | |
} | |
} | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
int y = now_princesses[2*i], x = now_princesses[2*i+1]; | |
if (board[2][y][x]) { | |
dead[1][i] = true; | |
board[1][y][x]--; | |
nowP--; | |
} | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
status[i] = 0; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
if (board[1][y][x]) { | |
status[i] = board[1][y][x]; | |
board[1][y][x] = 0; | |
board[0][y][x] = i+1; | |
} | |
} | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
int y = now_princesses[2*i], x = now_princesses[2*i+1]; | |
if (board[0][y][x] > 0) { | |
follow[i] = board[0][y][x]-1; | |
} | |
} | |
/* | |
if (debug < 50) { | |
debug++; | |
for (int ii = 0; ii < status.size(); ii++) { | |
cerr << status[ii] << " "; | |
} | |
cerr << endl; | |
} | |
*/ | |
} | |
int this_score = 0; | |
for (int i = 0; i < KK; i++) { | |
if (status[i] == -1) this_score -= 10; | |
if (status[i] > 0) this_score += status[i]*100; | |
} | |
score[sp][_G] += this_score; | |
} | |
} | |
} | |
//cerr << "monte " << monte << endl; | |
int best_score = -INF; | |
int _G; | |
for (int i = 0; i < 4; i++) { | |
for (int j = 1; j <= 3; j++) { | |
//cerr << best_score << " "; | |
if (score[i][j] > best_score) { | |
best_score = score[i][j]; | |
split = i; | |
_G = j; | |
} | |
} | |
//cerr << endl; | |
} | |
int rand_seed[4][5]; | |
rep(i,4) rep(j,5) rand_seed[i][j] = engine.rand(); | |
memset(score, 0, sizeof(score)); | |
while (getTime(start) < MONTE_TIME2) { | |
//cerr << "monte" << endl; | |
monte++; | |
int xorrnd = engine.rand(); | |
for (int u = 0; u < 4; u++) { | |
for (int v = 0; v < 5; v++) { | |
XorShift tmp_engine(xorrnd); | |
XorShift now_engine(rand_seed[u][v]); | |
dynamic_init(princesses, (int)(split!=0), KK, _G, split); | |
//cerr << "dy init" << endl; | |
status = vector<int>(KK, 0); | |
memset(dead, 0, sizeof(dead)); | |
memset(follow, -1, sizeof(follow)); | |
int nowP = princesses.size()/2, nowM = monsters.size()/2; | |
for (int i = 0; i < 2*P; i++) now_princesses[i] = princesses[i]; | |
for (int i = 0; i < 2*M; i++) now_monsters[i] = monsters[i]; | |
//cerr << "ok1" << endl; | |
for (int _ = 0; _ < 5*S; _++) { | |
//cerr << "ok2" << endl; | |
memset(board, 0, sizeof(board)); | |
memset(last_dead, 0, sizeof(last_dead)); | |
int tmpP = 0; | |
int tmpK = 0; | |
for (int i = 0; i < status.size(); i++) { | |
if (status[i] > 0) tmpP += status[i]; | |
if (status[i] >= 0) tmpK++; | |
} | |
if (split == 0) { | |
string tmp = split_move(status, nowP, nowM, INF, 0, tmpP, tmpK, now_engine); | |
} else { | |
string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), nowP, nowM, INF, 0, tmpP, tmpK, now_engine) | |
+ split_move(vector<int>(status.begin()+K[0], status.end()), nowP, nowM, INF, 1, tmpP, tmpK, now_engine); | |
} | |
if (split == 0) { | |
for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i]; | |
} else { | |
for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i]; | |
for (int i = 0; i < 2*K[1]; i++) now_knights[2*K[0]+i] = knights[1][i]; | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
board[0][now_knights[i*2]][now_knights[i*2+1]]++; | |
} | |
//cerr << "ok3" << endl; | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
if (follow[i] != -1) { | |
now_princesses[2*i] = now_knights[2*follow[i]]; | |
now_princesses[2*i+1] = now_knights[2*follow[i]+1]; | |
} else { | |
int r; | |
while (true) { | |
r = tmp_engine.rand()%5; | |
if (in_board(now_princesses[2*i]+dy[r], now_princesses[2*i+1]+dx[r])) break; | |
} | |
now_princesses[2*i] += dy[r]; | |
now_princesses[2*i+1] += dx[r]; | |
} | |
if (now_princesses[2*i] == 0) { | |
if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) { | |
dead[1][i] = true; | |
nowP--; | |
} | |
} else if (now_princesses[2*i] == S-1) { | |
if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) { | |
dead[1][i] = true; | |
nowP--; | |
} | |
} | |
if (!dead[1][i]) board[1][now_princesses[2*i]][now_princesses[2*i+1]]++; | |
} | |
//cerr << "ok4" << endl; | |
for (int i = 0; i < M; i++) { | |
if (dead[2][i]) continue; | |
int r; | |
while (true) { | |
r = tmp_engine.rand()%5; | |
if (in_board(now_monsters[2*i]+dy[r], now_monsters[2*i+1]+dx[r])) break; | |
} | |
now_monsters[2*i] += dy[r]; | |
now_monsters[2*i+1] += dx[r]; | |
board[2][now_monsters[2*i]][now_monsters[2*i+1]]++; | |
} | |
/* | |
if (debug < 10) { | |
debug++; | |
for (int i = 0; i < 3; i++) { | |
for (int j = 0; j < S; j++) { | |
for (int k = 0; k < S; k++) { | |
cerr << board[i][j][k] << " "; | |
} | |
cerr << endl; | |
} | |
cerr << endl; | |
} | |
} | |
*/ | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
int cntK = board[0][y][x]; | |
int cntM = board[2][y][x]; | |
if (cntK == 0 || cntM == 0) continue; | |
pair<int,int> result = battle(cntK, cntM); | |
board[0][y][x] -= (cntK-result.first); | |
last_dead[0][y][x] = cntK-result.first; | |
board[2][y][x] -= (cntM-result.second); | |
last_dead[2][y][x] = cntM-result.second; | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
if (last_dead[0][y][x] > 0) { | |
dead[0][i] = true; | |
last_dead[0][y][x]--; | |
status[i] = -1; | |
} | |
} | |
//cerr << "ok5" << endl; | |
for (int i = 0; i < M; i++) { | |
if (dead[2][i]) continue; | |
int y = now_monsters[2*i], x = now_monsters[2*i+1]; | |
if (last_dead[2][y][x] > 0) { | |
dead[2][i] = true; | |
last_dead[2][y][x]--; | |
nowM--; | |
} | |
} | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
int y = now_princesses[2*i], x = now_princesses[2*i+1]; | |
if (board[2][y][x]) { | |
dead[1][i] = true; | |
board[1][y][x]--; | |
nowP--; | |
} | |
} | |
for (int i = 0; i < KK; i++) { | |
if (dead[0][i]) continue; | |
status[i] = 0; | |
int y = now_knights[2*i], x = now_knights[2*i+1]; | |
if (board[1][y][x]) { | |
status[i] = board[1][y][x]; | |
board[1][y][x] = 0; | |
board[0][y][x] = i+1; | |
} | |
} | |
for (int i = 0; i < P; i++) { | |
if (dead[1][i]) continue; | |
int y = now_princesses[2*i], x = now_princesses[2*i+1]; | |
if (board[0][y][x] > 0) { | |
follow[i] = board[0][y][x]-1; | |
} | |
} | |
/* | |
if (debug < 50) { | |
debug++; | |
for (int ii = 0; ii < status.size(); ii++) { | |
cerr << status[ii] << " "; | |
} | |
cerr << endl; | |
} | |
*/ | |
} | |
int this_score = 0; | |
for (int i = 0; i < KK; i++) { | |
if (status[i] == -1) this_score -= 10; | |
if (status[i] > 0) this_score += status[i]*100; | |
} | |
score[u][v] += this_score; | |
} | |
} | |
} | |
//cerr << "monte " << monte << endl; | |
best_score = -INF; | |
for (int i = 0; i < 4; i++) { | |
for (int j = 0; j < 5; j++) { | |
//cerr << best_score << " "; | |
if (score[i][j] > best_score) { | |
best_score = score[i][j]; | |
best_engine = XorShift(rand_seed[i][j]); | |
} | |
} | |
//cerr << endl; | |
} | |
dynamic_init(princesses, (int)(split!=0), KK, _G, split); | |
//cerr << split << " " << _G << endl; | |
//cerr << "init end" << endl; | |
//cerr << string(K[0], (char)('0'+rec_index[0]))+string(K[1], (char)('0'+rec_index[1])) << endl; | |
if (split == 0) return string(K[0], (char)('0'+rec_index[0])); | |
else return string(K[0], (char)('0'+rec_index[0]))+string(K[1], (char)('0'+rec_index[1])); | |
} | |
string go_rectangle (int ind, XorShift now_engine) { | |
//cerr << "go_rectangle" << endl; | |
int r = now_engine.rand()%2; | |
int dir; | |
string ret; | |
if (rec_index[ind] == 0) { | |
if (knights[ind][0] == rec_edge[0]) dir = 1; | |
else if (knights[ind][1] == rec_edge[3]) dir = 2; | |
else dir = (r?1:2); | |
for (int i = 0; i < K[ind]; i++) { | |
knights[ind][i*2] += dy[dir]; | |
knights[ind][i*2+1] += dx[dir]; | |
} | |
for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]); | |
if (knights[ind][0] == rec_edge[0] && knights[ind][1] == rec_edge[3]) { | |
age[ind]++; | |
age_first_day[ind] = true; | |
} | |
} else if (rec_index[ind] == 1) { | |
if (knights[ind][0] == rec_edge[0]) dir = 3; | |
else if (knights[ind][1] == rec_edge[1]) dir = 2; | |
else dir = (r?3:2); | |
for (int i = 0; i < K[ind]; i++) { | |
knights[ind][i*2] += dy[dir]; | |
knights[ind][i*2+1] += dx[dir]; | |
} | |
for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]); | |
if (knights[ind][0] == rec_edge[0] && knights[ind][1] == rec_edge[1]) { | |
age[ind]++; | |
age_first_day[ind] = true; | |
} | |
} else if (rec_index[ind] == 2) { | |
if (knights[ind][0] == rec_edge[2]) dir = 3; | |
else if (knights[ind][1] == rec_edge[1]) dir = 0; | |
else dir = (r?3:0); | |
for (int i = 0; i < K[ind]; i++) { | |
knights[ind][i*2] += dy[dir]; | |
knights[ind][i*2+1] += dx[dir]; | |
} | |
for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]); | |
if (knights[ind][0] == rec_edge[2] && knights[ind][1] == rec_edge[1]) { | |
age[ind]++; | |
age_first_day[ind] = true; | |
} | |
} else { | |
if (knights[ind][0] == rec_edge[2]) dir = 1; | |
else if (knights[ind][1] == rec_edge[3]) dir = 0; | |
else dir = (r?1:0); | |
for (int i = 0; i < K[ind]; i++) { | |
knights[ind][i*2] += dy[dir]; | |
knights[ind][i*2+1] += dx[dir]; | |
} | |
for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]); | |
if (knights[ind][0] == rec_edge[2] && knights[ind][1] == rec_edge[3]) { | |
age[ind]++; | |
age_first_day[ind] = true; | |
} | |
} | |
rectangle[knights[ind][0]][knights[ind][1]] += K[ind]; | |
//cerr << "end_go_rectagle" << endl; | |
return ret; | |
} | |
string draw_rectangle (vector<int> status, int ind, XorShift now_engine) { | |
//cerr << "draw_rectangle" << endl; | |
if (age_first_day[ind]) { | |
Gsize[ind] = 0; | |
int entity_cnt = 0; | |
memset(Gindex[ind], 0, sizeof(Gindex[ind])); | |
for (int i = 0; i < K[ind]; i++) { | |
Gindex[ind][i] = Gsize[ind]; | |
if (status[i] != -1) { | |
entity_cnt++; | |
if (age[ind] > 1 && Gsize[ind] == 0) { | |
if (entity_cnt == min(G[ind],mainG)) { | |
Gsize[ind]++; | |
entity_cnt = 0; | |
} | |
} else if (entity_cnt == G[ind]) { | |
Gsize[ind]++; | |
entity_cnt = 0; | |
} | |
} | |
} | |
if (Gsize[ind] == 0) Gsize[ind] = 1; | |
for (int i = 0; i < K[ind]; i++) { | |
if (Gindex[ind][i] == Gsize[ind]) Gindex[ind][i] = 0; | |
} | |
for (int i = 0; i < Gsize[ind]; i++) { | |
Gknights[ind][2*i] = knights[ind][0]; | |
Gknights[ind][2*i+1] = knights[ind][1]; | |
} | |
} | |
//cerr << "mid_draw" << endl; | |
string ret; | |
for (int i = 0; i < Gsize[ind]; i++) { | |
//cerr << "0 "; | |
int r = now_engine.rand()%2; | |
int dir; | |
//cerr << rec_dir[ind][0] << " " << rec_dir[ind][1] << " "; | |
int toy[2] = {Gknights[ind][i*2]+dy[rec_dir[ind][0]], Gknights[ind][i*2]+dy[rec_dir[ind][1]]}; | |
int tox[2] = {Gknights[ind][i*2+1]+dx[rec_dir[ind][0]], Gknights[ind][i*2+1]+dx[rec_dir[ind][1]]}; | |
//cerr << "1 "; | |
if (age_first_day[ind] && i > Gsize[ind]/2) { | |
dir = 4; | |
} else if (!in_rectangle(toy[0], tox[0]) && !in_rectangle(toy[1], tox[1])) { | |
dir = 4; | |
} else if (!in_rectangle(toy[0], tox[0])) { | |
dir = rec_dir[ind][1]; | |
} else if (!in_rectangle(toy[1], tox[1])) { | |
dir = rec_dir[ind][0]; | |
} else { | |
if (rectangle[toy[0]][tox[0]] > rectangle[toy[1]][tox[1]]) { | |
dir = rec_dir[ind][1]; | |
} else if (rectangle[toy[0]][tox[0]] < rectangle[toy[1]][tox[1]]) { | |
dir = rec_dir[ind][0]; | |
} else { | |
dir = rec_dir[ind][r]; | |
} | |
} | |
//cerr << "2 "; | |
Gdir[ind][i] = dir; | |
Gknights[ind][2*i] += dy[dir]; | |
Gknights[ind][2*i+1] += dx[dir]; | |
rectangle[Gknights[ind][2*i]][Gknights[ind][2*i+1]]++; | |
//cerr << "3" << endl; | |
} | |
//cerr << "hun" << endl; | |
for (int i = 0; i < K[ind]; i++) { | |
knights[ind][2*i] += dy[Gdir[ind][Gindex[ind][i]]]; | |
knights[ind][2*i+1] += dx[Gdir[ind][Gindex[ind][i]]]; | |
ret.push_back(dir_str[Gdir[ind][Gindex[ind][i]]]); | |
} | |
//cerr << "mid2_draw" << endl; | |
age_first_day[ind] = false; | |
rec_len[ind]--; | |
if (rec_len[ind] < 0) { | |
age[ind]++; | |
G[ind]++; | |
age_first_day[ind] = true; | |
rec_dir[ind][0] = (rec_dir[ind][0]+2)%4; | |
rec_dir[ind][1] = (rec_dir[ind][1]+2)%4; | |
rec_len[ind] = 1+rec_edge[2]-rec_edge[0]+rec_edge[1]-rec_edge[3]; | |
} | |
//cerr << "end_draw" << endl; | |
return ret; | |
} | |
string end_game (int ind) { | |
//cerr << "end_game" << endl; | |
int rest_turn = end_turn-turn+1; | |
if (last_phase[ind]) { | |
for (int i = 0; i < 4; i++) { | |
int dis = distance(knights[ind][0], knights[ind][1], corner[i][0], corner[i][1]); | |
if (dis > rest_turn) continue; | |
if (i <= 1) { | |
if (knights[ind][0] != 0) { | |
knights[ind][0]--; | |
return string(K[ind], dir_str[0]); | |
} else { | |
if (i == 0) { | |
knights[ind][1]--; | |
return string(K[ind], dir_str[3]); | |
} else { | |
knights[ind][1]++; | |
return string(K[ind], dir_str[1]); | |
} | |
} | |
} else { | |
if (knights[ind][0] != S-1) { | |
knights[ind][0]++; | |
return string(K[ind], dir_str[2]); | |
} else { | |
if (i == 2) { | |
knights[ind][1]++; | |
return string(K[ind], dir_str[1]); | |
} else { | |
knights[ind][1]--; | |
return string(K[ind], dir_str[3]); | |
} | |
} | |
} | |
} | |
return string(K[ind], dir_str[4]); | |
} | |
string ret = string(K[ind], 'O'); | |
for (int k = 0; k < K[ind]; k++) { | |
for (int i = 0; i < 4; i++) { | |
int dis = distance(knights[ind][k*2], knights[ind][k*2+1], corner[i][0], corner[i][1]); | |
if (dis > rest_turn) continue; | |
if (i <= 1) { | |
if (knights[ind][k*2] != 0) { | |
knights[ind][k*2]--; | |
ret[k] = 'N'; | |
} else { | |
if (i == 0) { | |
knights[ind][2*k+1]--; | |
ret[k] = 'W'; | |
} else { | |
knights[ind][2*k+1]++; | |
ret[k] = 'E'; | |
} | |
} | |
} else { | |
if (knights[ind][2*k] != S-1) { | |
knights[ind][2*k]++; | |
ret[k] = 'S'; | |
} else { | |
if (i == 2) { | |
knights[ind][2*k+1]++; | |
ret[k] = 'E'; | |
} else { | |
knights[ind][2*k+1]--; | |
ret[k] = 'W'; | |
} | |
} | |
} | |
break; | |
} | |
} | |
return ret; | |
} | |
inline string clean_monsters(int ind) { | |
//cerr << "clean_monsters" << endl; | |
last_phase[ind] = true; | |
int dir; | |
if (last_south[ind]) { | |
if (last_east[ind]) { | |
if (knights[ind][1] == S-2) { | |
if (knights[ind][0] == S-2) { | |
last_east[ind] = false; | |
last_south[ind] = false; | |
dir = 3; | |
} else { | |
last_east[ind] = false; | |
dir = 2; | |
} | |
} else { | |
dir = 1; | |
} | |
} else { | |
if (knights[ind][1] == 1) { | |
if (knights[ind][0] == S-2) { | |
last_east[ind] = true; | |
last_south[ind] = true; | |
dir = 1; | |
} else { | |
last_east[ind] = true; | |
dir = 2; | |
} | |
} else { | |
dir = 3; | |
} | |
} | |
} else { | |
if (last_east[ind]) { | |
if (knights[ind][1] == S-2) { | |
if (knights[ind][0] == 1) { | |
last_east[ind] = false; | |
last_south[ind] = true; | |
dir = 3; | |
} else { | |
last_east[ind] = false; | |
dir = 0; | |
} | |
} else { | |
dir = 1; | |
} | |
} else { | |
if (knights[ind][1] == 1) { | |
if (knights[ind][0] == 1) { | |
last_east[ind] = true; | |
last_south[ind] = true; | |
dir = 1; | |
} else { | |
last_east[ind] = true; | |
dir = 0; | |
} | |
} else { | |
dir = 3; | |
} | |
} | |
} | |
/* | |
for (int i = 0; i < K*2; i += 2) { | |
knights[i] += dy[dir]; | |
knights[i+1] += dx[dir]; | |
} | |
*/ | |
knights[ind][0] += dy[dir]; | |
knights[ind][1] += dx[dir]; | |
return string(K[ind], dir_str[dir]); | |
} | |
// ---------------------------------------------- | |
string split_move (vector<int> status, int P, int M, int timeLeft, int ind, int nowP, int nowK, XorShift now_engine) { | |
//cerr << "hoge" << endl; | |
if (end_turn-turn <= S || timeLeft <= 500) { | |
return end_game(ind); | |
} | |
if (age[ind] == 0) { | |
return go_rectangle(ind, now_engine); | |
} | |
if (age_first_day[ind] == true && nowK < mainG) { | |
return end_game(ind); | |
} | |
if (P-nowP > 0 || age_first_day[ind] == false) { | |
return draw_rectangle(status, ind, now_engine); | |
} | |
if (nowK < mainG) return end_game(ind); | |
return clean_monsters(ind); | |
} | |
string move (vector<int> status, int P, int M, int timeLeft) { | |
turn++; | |
//cerr << "split " << split << endl; | |
int nowP = 0; | |
int nowK = 0; | |
for (int i = 0; i < status.size(); i++) { | |
if (status[i] > 0) nowP += status[i]; | |
if (status[i] >= 0) nowK++; | |
} | |
if (split == 0) { | |
return split_move(status, P, M, timeLeft, 0, nowP, nowK, best_engine); | |
} else { | |
string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), P, M, timeLeft, 0, nowP, nowK, best_engine) | |
+ split_move(vector<int>(status.begin()+K[0], status.end()), P, M, timeLeft, 1, nowP, nowK, best_engine); | |
//cerr << tmp << endl; | |
return tmp; | |
/* | |
return split_move(vector<int>(status.begin(), status.begin()+k[0]), p, m, timeleft, 0) | |
+ split_move(vector<int>(status.begin()+k[0], status.end()), p, m, timeleft, 1); | |
*/ | |
} | |
} | |
}; | |
// -------8<------- end of solution submitted to the website -------8<------- | |
template<class T> void getVector(vector<T>& v) { | |
for (int i = 0; i < v.size(); ++i) | |
cin >> v[i]; | |
} | |
int main() { | |
PrincessesAndMonsters pam; | |
int S, P, M, K; | |
cin >> S >> P; | |
vector<int> princesses(P); | |
getVector(princesses); | |
cin >> M; | |
vector<int> monsters(M); | |
getVector(monsters); | |
cin >> K; | |
string retInit = pam.initialize(S, princesses, monsters, K); | |
cout << retInit << endl; | |
cout.flush(); | |
for (int st = 0; ; ++st) { | |
int nK; | |
cin >> nK; | |
vector<int> status(K); | |
getVector(status); | |
int nP, nM; | |
cin >> nP >> nM; | |
int timeLeft; | |
cin >> timeLeft; | |
string ret = pam.move(status, nP, nM, timeLeft); | |
cout << ret << endl; | |
cout.flush(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment