oj.uz

답안 #130812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130812 2019-07-16T06:12:00 Z 윤교준(#3170) Snake (CEOI08_snake) C++14
0 / 100
 1000 ms 32772 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;

unordered_map<int, int> MP;
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);
	auto it = MP.find(a<<15|b);
	if(MP.end() != it) return it->second;
	int ret = INF;
	ret = f((a+K+1)>>1, (b+K+1)>>1) + 1;
	MP[a<<15|b] = ret;
	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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1626 ms 32124 KB Time limit exceeded
2 Runtime error 332 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 320 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 328 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 341 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 1635 ms 32144 KB Time limit exceeded
7 Runtime error 356 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 323 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 328 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 340 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 340 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 1648 ms 32132 KB Time limit exceeded
13 Runtime error 327 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 337 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 335 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Execution timed out 1646 ms 32100 KB Time limit exceeded
17 Runtime error 335 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 337 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 401 ms 32772 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 352 ms 32768 KB Execution killed with signal 9 (could be triggered by violating memory limits)