oj.uz

Submission #130836

# Submission time Handle Problem Language Result Execution time Memory
130836 2019-07-16T06:51:46 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
85 / 100
 140 ms 1604 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 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) mb = ma;
	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 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
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1496 KB Output is correct: estimate ok. 13 calls needed
2 Correct 135 ms 1472 KB Output is correct: estimate ok. 13 calls needed
3 Correct 136 ms 1464 KB Output is correct: estimate ok. 13 calls needed
4 Correct 135 ms 1472 KB Output is correct: estimate ok. 13 calls needed
5 Correct 136 ms 1576 KB Output is correct: estimate ok. 13 calls needed
6 Correct 135 ms 1524 KB Output is correct: estimate ok. 13 calls needed
7 Correct 135 ms 1492 KB Output is correct: estimate ok. 13 calls needed
8 Correct 134 ms 1472 KB Output is correct: estimate ok. 13 calls needed
9 Runtime error 135 ms 1492 KB Execution failed because the return code was nonzero
10 Runtime error 135 ms 1496 KB Execution failed because the return code was nonzero
11 Correct 135 ms 1400 KB Output is correct: estimate ok. 11 calls needed
12 Correct 134 ms 1532 KB Output is correct: estimate ok. 13 calls needed
13 Runtime error 135 ms 1492 KB Execution failed because the return code was nonzero
14 Correct 135 ms 1604 KB Output is correct: estimate ok. 13 calls needed
15 Correct 136 ms 1468 KB Output is correct: estimate ok. 13 calls needed
16 Correct 133 ms 1400 KB Output is correct: estimate ok. 13 calls needed
17 Correct 136 ms 1388 KB Output is correct: estimate ok. 13 calls needed
18 Correct 135 ms 1496 KB Output is correct: estimate ok. 13 calls needed
19 Correct 137 ms 1572 KB Output is correct: estimate ok. 13 calls needed
20 Correct 140 ms 1400 KB Output is correct: estimate ok. 13 calls needed