제출 #956049

#제출 시각아이디문제언어결과실행 시간메모리
956049MuntherCarrot동굴 (IOI13_cave)C++14
100 / 100
265 ms864 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; // int tryCombination(int S[]); // void answer(int S[], int D[]); #define ask(x) tryCombination(x) #define submit(x, y) answer(x, y) const int MAXN = 5010; int done[MAXN]; bool pos[MAXN]; int n; void solve(int x, vector<int> &vec){ int a[n] = {}; for(int i = 0; i < n; i++){ if(done[i] == -1) continue; a[i] = pos[done[i]]; } int l = 0, r = vec.size() - 1; pos[x] = (ask(a) == x); // 1 = colse, 0 = open while(l < r){ int mid = (l + r) / 2; // [l, mid], [mid + 1, r] for(int i = l; i <= mid; i++){ a[vec[i]] = 1; } int res = (ask(a) == x); if(res == pos[x]){ l = mid + 1; } else{ r = mid; } for(int i = l; i <= mid; i++){ a[vec[i]] = 0; } } done[vec[l]] = x; // cout << vec[l] << ' ' << (ask(a) != pos[x] ? "yes" : "no") << endl; } void exploreCave(int N){ memset(done, -1, sizeof done); n = N; for(int i = 0; i < n; i++){ vector<int> vec; for(int j = 0; j < n; j++){ if(done[j] != -1) continue; vec.push_back(j); } solve(i, vec); } int ans1[n], ans2[n]; for(int i = 0; i < n; i++){ ans1[i] = pos[done[i]]; ans2[i] = done[i]; } submit(ans1, ans2); } // by me
#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...