Submission #1035423

#TimeUsernameProblemLanguageResultExecution timeMemory
1035423vaneaCave (IOI13_cave)C++14
100 / 100
216 ms600 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; using ll = long long; const int mxN = 5e3+10; bool vis[mxN]; bool check(int l, int r, int elem, int n, int arr[], int i) { for(int j = l; j <= r; j++) { if(vis[j]) continue; arr[j] = 1-elem; } int k = tryCombination(arr); for(int j = l; j <= r; j++) { if(vis[j]) continue; arr[j] = elem; } return ((k == -1) || (k > i)); } void exploreCave(int n) { int ans[n], d[n]; for(int i = 0; i < n; i++) { int elem; int curr[n]; memset(curr, 0, sizeof curr); for(int j = 0; j < n; j++) { if(vis[j]) curr[j] = ans[j]; } int k = tryCombination(curr); if(k > i || k == -1) elem = 1; else elem = 0; for(int j = 0; j < n; j++) { if(vis[j]) curr[j] = ans[j]; else curr[j] = elem; } int l = 0, r = n-1; while(l < r) { int mid = (l+r+1)/2; if(check(mid, r, elem, n, curr, i)) { l = mid; } else r = mid-1; } d[l] = i; ans[l] = (1-elem); vis[l] = true; } answer(ans, 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...