| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 130830 |
2019-07-16T06:46:04 Z |
윤교준(#3170) |
Snake (CEOI08_snake) |
C++14 |
|
142 ms |
1556 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) {
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;
if(la+lb <= K*2+2) answer(max(0, bs-ae-1) + (la+lb+1)/2);
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((l+1)>>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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
134 ms |
1400 KB |
Output is correct: estimate ok. 13 calls needed |
| 2 |
Correct |
136 ms |
1448 KB |
Output is correct: estimate ok. 13 calls needed |
| 3 |
Correct |
134 ms |
1400 KB |
Output is correct: estimate ok. 13 calls needed |
| 4 |
Correct |
139 ms |
1472 KB |
Output is correct: estimate ok. 13 calls needed |
| 5 |
Incorrect |
134 ms |
1468 KB |
your estimate differs too much (9 units) |
| 6 |
Correct |
134 ms |
1448 KB |
Output is correct: estimate ok. 13 calls needed |
| 7 |
Incorrect |
135 ms |
1556 KB |
your estimate differs too much (2 units) |
| 8 |
Incorrect |
136 ms |
1500 KB |
your estimate differs too much (3 units) |
| 9 |
Runtime error |
135 ms |
1504 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 |
1500 KB |
Output is correct: estimate ok. 13 calls needed |
| 12 |
Correct |
133 ms |
1448 KB |
Output is correct: estimate ok. 13 calls needed |
| 13 |
Runtime error |
135 ms |
1400 KB |
Execution failed because the return code was nonzero |
| 14 |
Correct |
136 ms |
1500 KB |
Output is correct: estimate ok. 13 calls needed |
| 15 |
Correct |
136 ms |
1496 KB |
Output is correct: estimate ok. 13 calls needed |
| 16 |
Correct |
135 ms |
1544 KB |
Output is correct: estimate ok. 13 calls needed |
| 17 |
Incorrect |
135 ms |
1448 KB |
your estimate differs too much (2 units) |
| 18 |
Correct |
135 ms |
1400 KB |
Output is correct: estimate ok. 13 calls needed |
| 19 |
Correct |
135 ms |
1492 KB |
Output is correct: estimate ok. 13 calls needed |
| 20 |
Correct |
142 ms |
1508 KB |
Output is correct: estimate ok. 13 calls needed |
