Submission #530067

#TimeUsernameProblemLanguageResultExecution timeMemory
530067buidangnguyen05Cave (IOI13_cave)C++14
100 / 100
798 ms548 KiB
/* input */ #include "cave.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e3; int n, done[N], state[N], que[N]; int query(int cnt) { for (int i = 0; i < n; ++i) { if (done[i] != -1) que[i] = state[i]; else if (cnt > 0) que[i] = 1, --cnt; else que[i] = 0; } return tryCombination(que); } void exploreCave(int _n) { memset(done, -1, sizeof(done)); n = _n; int prev = query(0); for (int i = 0; i < n; ++i) { int L = 0, R = n, cnt = 0; while (L <= R) { int mid = (L + R) >> 1; int cur = query(mid); if ((prev == i && cur != i) || (prev != i && cur == i)) { cnt = mid; R = mid - 1; } else L = mid + 1; } int pos = 0; for (; ; ++pos) { cnt -= (done[pos] == -1); if (!cnt) break; } if (prev == i) state[pos] = 1; done[pos] = i; prev = query(0); } answer(state, done); }
#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...