oj.uz

Submission #130838

# Submission time Handle Problem Language Result Execution time Memory
130838 2019-07-16T06:55:13 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
100 / 100
 139 ms 1632 KB 
#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 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;

inline void answer(int l) { tell_length(min(L-K, max(K+1, l))); exit(0); }
void solveLine(int,int);

void solveSplit(int as, int ae, int bs, int be) {
	if(L < ae) ae = L;
	if(L < be) be = L;
	if(be < ae) ae = be;
	if(bs < as) bs = as;
	if(as == ae && bs == be) answer(be-as+1);
	int la = ae-as+1, lb = be-bs+1;
	int hls = max(1, bs-ae+1), hle = min(L, be-as+1), hlmid = (hls+hle) >> 1;
	if(hlmid-hls <= K && hle-hlmid <= K) answer(hlmid);
	int lma = (la+K+1)>>1, lmb = (lb+K+1)>>1;
	int ma = min(L, as+lma-1), mb = min(L, bs+lmb);
	if(mb <= ma) ma = mb-1;
	int ret = ask(ma, mb);
	if(1 == ret) solveSplit(as, ma, bs, mb-1);
	else if(4 == ret) solveSplit(as, ma, mb, min(L, be+K));
	else if(2 == ret) solveSplit(ma+1, min({L, ae+K, mb-1}), bs, mb-1);
	else if(5 == ret) solveSplit(ma+1, min(L, ae+K), mb, min(L, be+K));
	else if(!ret) solveLine(as, ma-1);
	else if(8 == ret) solveLine(mb+1, min(L, be+K));
	else fuk();
}


void solveLine(int s, int e) {
	if(s < 1) s = 1;
	if(L < e) e = L;
	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, e+K));
	else if(1 == ret) solveSplit(s, a, a, b-1);
	else if(5 == ret) solveSplit(a+1, b, b, min(L, e+K));
	else if(4 == ret) solveSplit(s, a, b, min(L, 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1528 KB Output is correct: estimate ok. 13 calls needed
2 Correct 137 ms 1620 KB Output is correct: estimate ok. 13 calls needed
3 Correct 135 ms 1632 KB Output is correct: estimate ok. 13 calls needed
4 Correct 137 ms 1468 KB Output is correct: estimate ok. 13 calls needed
5 Correct 135 ms 1596 KB Output is correct: estimate ok. 13 calls needed
6 Correct 134 ms 1496 KB Output is correct: estimate ok. 13 calls needed
7 Correct 135 ms 1472 KB Output is correct: estimate ok. 13 calls needed
8 Correct 139 ms 1440 KB Output is correct: estimate ok. 13 calls needed
9 Correct 136 ms 1496 KB Output is correct: estimate ok. 13 calls needed
10 Correct 135 ms 1432 KB Output is correct: estimate ok. 13 calls needed
11 Correct 135 ms 1532 KB Output is correct: estimate ok. 11 calls needed
12 Correct 134 ms 1448 KB Output is correct: estimate ok. 13 calls needed
13 Correct 139 ms 1564 KB Output is correct: estimate ok. 10 calls needed
14 Correct 135 ms 1608 KB Output is correct: estimate ok. 13 calls needed
15 Correct 135 ms 1448 KB Output is correct: estimate ok. 13 calls needed
16 Correct 134 ms 1576 KB Output is correct: estimate ok. 13 calls needed
17 Correct 135 ms 1400 KB Output is correct: estimate ok. 13 calls needed
18 Correct 135 ms 1472 KB Output is correct: estimate ok. 13 calls needed
19 Correct 135 ms 1492 KB Output is correct: estimate ok. 13 calls needed
20 Correct 135 ms 1604 KB Output is correct: estimate ok. 13 calls needed