제출 #867738

#제출 시각아이디문제언어결과실행 시간메모리
867738Dec0Dedd동굴 (IOI13_cave)C++14
100 / 100
595 ms856 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; void exploreCave(int n) { int ans[n]={}, d[n]={}; memset(ans, -1, sizeof(ans)); memset(d, -1, sizeof(d)); for (int i=0; i<n; ++i) { int s[n+1]={}; // check if i-th must be up for (int j=0; j<n; ++j) { if (ans[j] != -1) s[j]=d[j]; else s[j]=0; } int k=0, x=tryCombination(s); if (x > i || x == -1) k=0; else k=1; int l=0, r=n-1, res=n-1; while (l <= r) { int m=(l+r)/2; int tp[n]={}; for (int j=0; j<n; ++j) { if (ans[j] != -1) tp[j]=d[j]; else { if (j <= m) tp[j]=k; else tp[j]=k^1; } } x=tryCombination(tp); if (x > i || x == -1) r=m-1, res=m; else l=m+1; } ans[res]=i, d[res]=k; } answer(d, ans); }
#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...