oj.uz

Submission #130813

# Submission time Handle Problem Language Result Execution time Memory
130813 2019-07-16T06:13:51 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
0 / 100
 1000 ms 1832 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(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;

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);
	int a = DA[l], b = DB[l];
	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 <= 0 || b <= 0) return 0;
	if(a+b <= K*2+2) return 0;
	if(a > b) swap(a, b);
	int ret = INF;
	ret = f((a+K+1)>>1, (b+K+1)>>1) + 1;
	return ret;
}

int g(int L) {
	if(L <= K*2+1) return 0;
	if(chkD[L]) return D[L];
	chkD[L] = true;
	int &ret = D[L]; ret = INF;
	int s = 1, e = 15; for(int m; s < e;) {
		m = (s+e) >> 1;
		bool flag = false;
		for(int a = 1; a < L; a++) {
			if(m <= g(a-1)) continue;
			int be = min(L, FMX[a+K][m-1]+a);
			for(int b = max({a+1, L+1+K - FMX[a+K][m-1], K}); b <= be; b++) {
				if(max({g(b-a-1), g(L-b+K), f(b-a, L-b+1+K)}) + 1 <= m) {
					flag = true;
					break;
				}
			}
			if(flag) break;
		}
		if(flag) e = m;
		else s = m+1;
	}
	ret = s;
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1121 ms 1676 KB Time limit exceeded
2 Execution timed out 1115 ms 1832 KB Time limit exceeded
3 Execution timed out 1117 ms 1548 KB Time limit exceeded
4 Execution timed out 1134 ms 1656 KB Time limit exceeded
5 Execution timed out 1118 ms 1784 KB Time limit exceeded
6 Execution timed out 1120 ms 1608 KB Time limit exceeded
7 Execution timed out 1119 ms 1784 KB Time limit exceeded
8 Execution timed out 1124 ms 1620 KB Time limit exceeded
9 Runtime error 1130 ms 1540 KB Execution failed because the return code was nonzero
10 Runtime error 1119 ms 1520 KB Execution failed because the return code was nonzero
11 Execution timed out 1120 ms 1704 KB Time limit exceeded
12 Execution timed out 1118 ms 1656 KB Time limit exceeded
13 Runtime error 1121 ms 1548 KB Execution failed because the return code was nonzero
14 Execution timed out 1117 ms 1560 KB Time limit exceeded
15 Execution timed out 1119 ms 1676 KB Time limit exceeded
16 Execution timed out 1120 ms 1688 KB Time limit exceeded
17 Execution timed out 1125 ms 1708 KB Time limit exceeded
18 Execution timed out 1122 ms 1604 KB Time limit exceeded
19 Execution timed out 1122 ms 1560 KB Time limit exceeded
20 Execution timed out 1115 ms 1660 KB Time limit exceeded