답안 #130821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130821	2019-07-16T06:23:26 Z	윤교준(#3170)	Snake (CEOI08_snake)	C++14	55 / 100	142 ms	1584 KB

snake

#include "snakelib.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
inline void fuk() { puts("ERR!"); exit(-1); }
inline void answer(int l) { tell_length(max(1, l)); exit(0); }
inline int ask(int s, int e) {
	char a, b;
	ask_snake(s-1, e-1, &a, &b);
	int ret = 0;
	if('s' == b) ret = 1;
	if('b' == b) ret = 2;
	ret *= 3;
	if('s' == a) ret += 1;
	if('b' == a) ret += 2;
	return ret;
}

const int MAXL = 12222;

const int GMX[11][14] = {
	{ 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12122 },
	{ 3, 0, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12122 },
	{ 5, 0, 7, 13, 25, 49, 97, 193, 385, 769, 1537, 3073, 6145, 12122 },
	{ 7, 0, 8, 14, 26, 50, 98, 194, 386, 770, 1538, 3074, 6146, 12122 },
	{ 9, 0, 0, 15, 27, 51, 99, 195, 387, 771, 1539, 3075, 6147, 12122 },
	{ 11, 0, 0, 16, 28, 52, 100, 196, 388, 772, 1540, 3076, 6148, 12122 },
	{ 13, 0, 0, 17, 29, 53, 101, 197, 389, 773, 1541, 3077, 6149, 12122 },
	{ 15, 0, 0, 18, 30, 54, 102, 198, 390, 774, 1542, 3078, 6150, 12122 },
	{ 17, 0, 0, 19, 31, 55, 103, 199, 391, 775, 1543, 3079, 6151, 12122 },
	{ 19, 0, 0, 20, 32, 56, 104, 200, 392, 776, 1544, 3080, 6152, 12122 },
	{ 21, 0, 0, 0, 33, 57, 105, 201, 393, 777, 1545, 3081, 6153, 12122 }
};
int FMX[MAXL][22];

int D[MAXL], DA[MAXL], DB[MAXL];
bitset<MAXL> chkD;

int L = 12122;
int K;


void solveSplit(int as, int ae, int bs, int be) {
	int la = ae-as+1, lb = be-bs+1;
	if(la+lb <= K*2+2) answer(bs-ae-1 + (la+lb+1)/2);
	int lma = (la+K+1)>>1, lmb = (lb+K+1)>>1;
	int ma = min(L-1, as+lma-1), mb = min(L-1, bs+lmb);
	int ret = ask(ma, mb);
	if(1 == ret) solveSplit(as, ma, bs, mb-1);
	else if(4 == ret) solveSplit(as, ma, mb, min(L-1, be+K));
	else if(2 == ret) solveSplit(ma+1, min(L-1, ae+K), bs, mb-1);
	else if(5 == ret) solveSplit(ma+1, min(L-1, ae+K), mb, min(L-1, be+K));
	else fuk();
}


void solveLine(int s, int e) {
	int l = e-s+1;
	if(l <= K*2+1) answer(K+1);
	int a = DA[l], b = DB[l];
	a += s-1; b += s-1;
	int ret = ask(a, b);
	if(!ret) solveLine(s, a-1);
	else if(2 == ret) solveLine(a+1, b-1);
	else if(8 == ret) solveLine(b+1, min(L-1, e+K));
	else if(1 == ret) solveSplit(s, a, a, b-1);
	else if(5 == ret) solveSplit(a+1, b, b, min(L-1, e+K));
	else if(4 == ret) solveSplit(s, a, b, min(L-1, e+K));
	else fuk();
}




int f(int a, int b) {
	if(a+b <= K*2+2) return 0;
	return f((a+K+1)>>1, (b+K+1)>>1) + 1;
}

int g(int L) {
	if(L <= K*2+1) return 0;
	if(chkD[L]) return D[L];
	chkD[L] = true;
	int &ret = D[L];
	for(int i = 0; i <= 13; i++) if(L <= GMX[K][i]) {
		ret = i;
		break;
	}
	int s = ret;
	for(int a = 1; a < L; a++) {
		bool flag = false;
		if(s <= g(a-1)) continue;
		int be = min(L, FMX[a+K][s-1]+a);
		for(int b = max({a+1, L+1+K - FMX[a+K][s-1], K}); b <= be; b++) {
			if(max({g(b-a-1), g(L-b+K), f(b-a, L-b+1+K)}) + 1 <= s) {
				flag = true;
				DA[L] = a; DB[L] = b;
				break;
			}
		}
		if(flag) break;
	}
	return ret;
}

int main() {
	K = get_speed();
	for(int i = 0; i <= L; i++) {
		for(int j = 0; j <= 15; j++) {
			int s = 0, e = L; for(int m; s < e;) {
				m = (s+e+1) >> 1;
				if(j < f(i, m)) e = m-1;
				else s = m;
			}
			FMX[i][j] = s;
		}
	}
	for(int i = 0; i <= L; i++) if(13 < g(i)) fuk();

	solveLine(1, L);
	return 0;
}

Subtask #1

55.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	135 ms	1400 KB	your estimate differs too much (1 units)
2	Correct	141 ms	1552 KB	Output is correct: estimate ok. 13 calls needed
3	Correct	136 ms	1564 KB	Output is correct: estimate ok. 13 calls needed
4	Correct	135 ms	1560 KB	Output is correct: estimate ok. 13 calls needed
5	Correct	136 ms	1532 KB	Output is correct: estimate ok. 13 calls needed
6	Incorrect	141 ms	1528 KB	your estimate differs too much (1 units)
7	Incorrect	142 ms	1552 KB	your estimate differs too much (2 units)
8	Incorrect	142 ms	1400 KB	your estimate differs too much (3 units)
9	Runtime error	135 ms	1576 KB	Execution failed because the return code was nonzero
10	Runtime error	135 ms	1528 KB	Execution failed because the return code was nonzero
11	Correct	135 ms	1476 KB	Output is correct: estimate ok. 13 calls needed
12	Correct	134 ms	1448 KB	Output is correct: estimate ok. 13 calls needed
13	Runtime error	135 ms	1496 KB	Execution failed because the return code was nonzero
14	Correct	136 ms	1560 KB	Output is correct: estimate ok. 13 calls needed
15	Correct	140 ms	1528 KB	Output is correct: estimate ok. 13 calls needed
16	Incorrect	138 ms	1584 KB	your estimate differs too much (1 units)
17	Incorrect	136 ms	1400 KB	your estimate differs too much (2 units)
18	Correct	136 ms	1396 KB	Output is correct: estimate ok. 13 calls needed
19	Correct	136 ms	1452 KB	Output is correct: estimate ok. 13 calls needed
20	Correct	136 ms	1556 KB	Output is correct: estimate ok. 13 calls needed