Submission #1172086

#TimeUsernameProblemLanguageResultExecution timeMemory
1172086jakubmz2Cave (IOI13_cave)C++20
100 / 100
273 ms556 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; typedef long long ll; const int MAXN = 5e3 + 5; int ktory[MAXN]; int good[MAXN]; int query(int a, int b, int kt, int n){ int q[n]; for(int i = 0; i < n; ++i){ if(good[i] != -1){ q[i] = good[i]; } else{ if(i >= a and i <= b){ q[i] = kt; } else{ q[i] = (kt ^ 1); } } } return tryCombination(q); } void obl(int i, int n){ int q[n]; for(int i = 0; i < n; ++i){ if(good[i] != -1){ q[i] = good[i]; } else{ q[i] = 0; } } int j = tryCombination(q); int kt; if(j > i or j == -1){ kt = 0; } else{ kt = 1; } //cout << kt << "\n"; int p = 0; int k = n - 1; int x, y; while(p != k){ int sr = (p + k) / 2; //cout << p << " " << sr << " " << kt << "\n"; for(int i = p; i <= k; ++i){ if(good[i] != -1){ q[i] = good[i]; } else{ if(i <= sr){ q[i] = kt; } else{ q[i] = (kt ^ 1); } } } int x = tryCombination(q); if(x > i or x == -1){ k = sr; } else{ for(int i = p; i <= k; ++i){ if(good[i] != -1){ q[i] = good[i]; } else{ if(i <= sr){ q[i] = (kt ^ 1); } else{ q[i] = kt; } } } p = sr + 1; } } //cout << i << " " << p << "\n"; good[p] = kt; ktory[p] = i; return; } void exploreCave(int n){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i = 0; i < n; ++i){ good[i] = -1; ktory[i] = -1; } for(int i = 0; i < n; ++i){ obl(i, n); } int U[n]; int P[n]; for(int i = 0; i < n; ++i){ U[i] = good[i]; P[i] = ktory[i]; } answer(U, P); 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...