제출 #56385

#제출 시각아이디문제언어결과실행 시간메모리
56385aquablitz11동굴 (IOI13_cave)C++14
100 / 100
402 ms640 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; const int N = 5010; int n, S[N], P[N], Q[N]; int test() { int x = tryCombination(Q); if (x == -1) x = n; return x; } void recur(int l, int r, int d, bool ori) // close = 1, open = 0 { if (l == r) { P[l] = d; S[l] = ori ? 1 : 0; } else { int m = (l+r)/2; for (int i = l; i <= m; ++i) { if (S[i] == -1) Q[i] = 1; } for (int i = m+1; i <= r; ++i) { if (S[i] == -1) Q[i] = 0; } bool ret = test() <= d; if (ori == ret) recur(m+1, r, d, ori); else recur(l, m, d, ori); } } void find_ans(int d) { for (int i = 0; i < n; ++i) { Q[i] = max(0, S[i]); } bool ret = test() <= d; recur(0, n-1, d, ret); } void exploreCave(int n) { ::n = n; for (int i = 0; i < n; ++i) P[i] = S[i] = -1; for (int i = 0; i < n; ++i) find_ans(i); answer(S, P); }
#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...