제출 #132203

#제출 시각아이디문제언어결과실행 시간메모리
132203junodeveloper동굴 (IOI13_cave)C++14
100 / 100
542 ms632 KiB
#include "cave.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() using namespace std; int S[5010], D[5010], cur, idx, nxt, x, W, n; int Try() { int r = tryCombination(S); return r == -1 ? n : r; } void FindAll(int s, int e, int p) { vector<int> a; for(int i=s; i<=e; i++) if(D[i] == -1) a.push_back(i); int B = (sz(a) + 1) / 2; bool flag = true, same = true; for(int i=0; i<sz(a); i+=B) { int rgt = min(sz(a), i+B), r = -1; for(int j=i; j<rgt; j++) S[a[j]] ^= 1; if(B > 2 && !same && p < idx && p != -1) { r = p; } else if(flag || B == 1) r = Try(); for(int j=i; j<rgt; j++) S[a[j]] ^= 1; if(r != p) same = false; if(r != idx) { if(B == 1) { if(idx < r) { D[a[i]] = idx; W = a[i]; nxt = r; x--; } else if(r < idx) D[a[i]] = r; } else FindAll(a[i], a[rgt - 1], r); } else flag = false; if(!x) break; } } void exploreCave(int N) { srand(123); n = N; memset(D, -1, sizeof(D)); for(int i=0; i<n; i++) S[i] = rand() % 2; cur = 0; nxt = Try(); while(cur < n) { idx = nxt; x = idx - cur + 1; FindAll(0, n - 1, -1); if(idx < n) S[W] ^= 1; cur = idx + 1; } answer(S, D); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...