Skip to content

Instantly share code, notes, and snippets.

@gasin

gasin/solution.cpp

Created February 22, 2018 02:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gasin/c83a205ea0486a674af69caac64fc842 to your computer and use it in GitHub Desktop.
Save gasin/c83a205ea0486a674af69caac64fc842 to your computer and use it in GitHub Desktop.
Download ZIP
MM98
Raw
solution.cpp
// 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