oj.uz

Submission #130834

# Submission time Handle Problem Language Result Execution time Memory
130834 2019-07-16T06:50:15 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
85 / 100
 171 ms 1588 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);
	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 1580 KB Output is correct: estimate ok. 13 calls needed
2 Correct 135 ms 1504 KB Output is correct: estimate ok. 13 calls needed
3 Correct 135 ms 1564 KB Output is correct: estimate ok. 13 calls needed
4 Correct 137 ms 1432 KB Output is correct: estimate ok. 13 calls needed
5 Correct 171 ms 1416 KB Output is correct: estimate ok. 13 calls needed
6 Correct 135 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 135 ms 1588 KB Output is correct: estimate ok. 13 calls needed
9 Runtime error 135 ms 1428 KB Execution failed because the return code was nonzero
10 Runtime error 135 ms 1400 KB Execution failed because the return code was nonzero
11 Correct 135 ms 1512 KB Output is correct: estimate ok. 11 calls needed
12 Correct 134 ms 1528 KB Output is correct: estimate ok. 13 calls needed
13 Runtime error 135 ms 1536 KB Execution failed because the return code was nonzero
14 Correct 135 ms 1588 KB Output is correct: estimate ok. 13 calls needed
15 Correct 135 ms 1472 KB Output is correct: estimate ok. 13 calls needed
16 Correct 134 ms 1400 KB Output is correct: estimate ok. 13 calls needed
17 Correct 135 ms 1576 KB Output is correct: estimate ok. 13 calls needed
18 Correct 136 ms 1448 KB Output is correct: estimate ok. 13 calls needed
19 Correct 135 ms 1428 KB Output is correct: estimate ok. 13 calls needed
20 Correct 167 ms 1400 KB Output is correct: estimate ok. 13 calls needed