oj.uz

답안 #130814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130814 2019-07-16T06:17:05 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(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;

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]; 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1126 ms 1704 KB Time limit exceeded
2 Execution timed out 1129 ms 1508 KB Time limit exceeded
3 Execution timed out 1128 ms 1692 KB Time limit exceeded
4 Execution timed out 1257 ms 1732 KB Time limit exceeded
5 Execution timed out 1139 ms 1708 KB Time limit exceeded
6 Execution timed out 1136 ms 1524 KB Time limit exceeded
7 Execution timed out 1127 ms 1676 KB Time limit exceeded
8 Execution timed out 1122 ms 1472 KB Time limit exceeded
9 Runtime error 1129 ms 1656 KB Execution failed because the return code was nonzero
10 Runtime error 1123 ms 1704 KB Execution failed because the return code was nonzero
11 Execution timed out 1131 ms 1656 KB Time limit exceeded
12 Execution timed out 1134 ms 1696 KB Time limit exceeded
13 Runtime error 1127 ms 1644 KB Execution failed because the return code was nonzero
14 Execution timed out 1122 ms 1576 KB Time limit exceeded
15 Execution timed out 1130 ms 1832 KB Time limit exceeded
16 Execution timed out 1123 ms 1544 KB Time limit exceeded
17 Execution timed out 1126 ms 1528 KB Time limit exceeded
18 Execution timed out 1242 ms 1576 KB Time limit exceeded
19 Execution timed out 1135 ms 1832 KB Time limit exceeded
20 Execution timed out 1263 ms 1816 KB Time limit exceeded