제출 #1099745

#제출 시각아이디문제언어결과실행 시간메모리
1099745spycoderyt동굴 (IOI13_cave)C++17
100 / 100
259 ms1108 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int n) { // int l = 0; // vector<int> v(n),a(n); // for(int i = 0;i<n;i++)a[i]=i; // while(l<n) { // int ans = tryCombination(v.data()); // if(ans>l || ans == -1)l++; // else v[l]^=1,l++; // } // answer(v.data(),a.data()); // vector<int> v(n),a(n); // for(int i = 0;i<n;i++) { // v[i]^=1; // a[i] = tryCombination(v.data()); // v[i]^=1; // } // answer(v.data(),a.data()); vector<int> v(n),a(n),d(n),tmp; // vec ans done for(int i = 0;i<n;i++) { // iterate over doors int l = 0, r = n-1; //bsearch on switch int res = tryCombination(v.data()); int can = ((res > i) || (res == -1) ? 1 : 0); // 1 if up to i is open, 0 if i is closed while(l<r) { int mid = (l+r)/2; tmp = v; for(int i = l;i<=mid;i++) if(!d[i])tmp[i]^=1; if(can) { // want to close it if(tryCombination(tmp.data()) == i) r = mid; else l = mid+1; } else { // want to open it res = tryCombination(tmp.data()); if(res > i || res == -1) r = mid; else l = mid+1; } } d[r]=1; a[r] = i; if(can==0)v[r]^=1; } answer(v.data(),a.data()); }
#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...