oj.uz

Submission #130821

# Submission time Handle Problem Language Result Execution time Memory
130821 2019-07-16T06:23:26 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
55 / 100
 142 ms 1584 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 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

# Verdict Execution time Memory 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