Submission #1208571

#TimeUsernameProblemLanguageResultExecution timeMemory
1208571peraCave (IOI13_cave)C++20
13 / 100
268 ms588 KiB
#include<bits/stdc++.h> #include "cave.h" using namespace std; void exploreCave(int N) { int S[N] , D[N] , W[N]; memset(S , 0 , sizeof(S)); memset(W , 0 , sizeof(W)); int u; while(true){ u = tryCombination(W); if(u == -1){ break; } vector<int> v; for(int i = 0;i < N;i ++){ if(W[i] == 0){ v.emplace_back(i); } } auto assign = [&](int m){ for(int i = 0;i <= m;i ++){ W[v[i]] = 1; } int A = tryCombination(W); for(int i = 0;i <= m;i ++){ W[v[i]] = 0; } return (A != u); }; int l = 0 , r = (int)v.size() - 1 , ans = -1; while(l <= r){ int m = (l + r) / 2; if(assign(m)){ ans = m; r = m - 1; }else{ l = m + 1; } } ans = v[ans]; S[ans] = W[ans] = 1; D[ans] = u; } for(int i = 0;i < N;i ++){ W[i] = 1; } while(true){ u = tryCombination(W); if(u == -1){ break; } vector<int> v; for(int i = 0;i < N;i ++){ if(W[i] == 1 && !S[i]){ v.emplace_back(i); } } auto assign = [&](int m){ for(int i = 0;i <= m;i ++){ W[v[i]] = 0; } int A = tryCombination(W); for(int i = 0;i <= m;i ++){ W[v[i]] = 1; } return (A != u); }; int l = 0 , r = (int)v.size() - 1 , ans; while(l <= r){ int m = (l + r) / 2; if(assign(m)){ ans = m; r = m - 1; }else{ l = m + 1; } } ans = v[ans]; S[ans] = W[ans] = 0; D[ans] = u; } answer(S , D); return; }
#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...