제출 #99282

#제출 시각아이디문제언어결과실행 시간메모리
99282long10024070동굴 (IOI13_cave)C++11
100 / 100
1659 ms640 KiB
#define Link "https://oj.uz/problem/view/IOI13_cave?fbclid=IwAR2HAQQWHxbplVnmFGboqMw4yr-N9sR3mRA2usvk6rTocr7u5QYaZIyHqxw" #include <iostream> #include <cstdio> #define TASK "Cave" using namespace std; const int maxn = 5e3 + 10; int n,s[maxn],True[maxn],Val[maxn],realval[maxn],reals[maxn]; #ifdef LHL int tryCombination(int s[]) { int res = n; for (int i=0;i<n;++i) if (s[i] != reals[i]) res = min(res,realval[i]); return res == n ? -1 : res; } void answer(int True[], int Val[]) { for (int i=0;i<n;++i) cout << True[i] << ' '; cout << '\n'; for (int i=0;i<n;++i) cout << Val[i] << ' '; } #else #include "cave.h" #endif // LHL void Fill(int l, int r, int d) { for (int i=l;i<=r;++i) if (Val[i] != -1) s[i] = True[i]; else s[i] = d; } void exploreCave(int n) { fill(Val,Val+n,-1); for (int i=0;i<n;++i) { Fill(0,n-1,0); bool fl = (i == tryCombination(s)); int l = 0; int r = n - 1; while (l <= r) { int m = (l + r) / 2; Fill(1,n-1,fl^1); Fill(l,m,fl); Fill(m+1,r,fl^1); if (tryCombination(s) == i) l = m + 1; else r = m - 1; } True[l] = fl; Val[l] = i; } answer(True,Val); } #ifdef LHL void Enter() { cin >> n; for (int i=0;i<n;++i) cin >> reals[i]; for (int i=0;i<n;++i) cin >> realval[i]; } void Init() { } void Solve() { exploreCave(n); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen(".INP","r",stdin); freopen(".OUT","w",stdout); Enter(); Init(); Solve(); } #else #endif //LHL
#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...