Submission #1260947

#TimeUsernameProblemLanguageResultExecution timeMemory
1260947repmann동굴 (IOI13_cave)C++20
100 / 100
498 ms556 KiB
#include <bits/stdc++.h> #include "cave.h" using namespace std; int N; int S[5000], T[5000], O[5000]; //int tryS[5000], tryO[5000], temp[5000]; //int tryCombination(int S[]) //{ // cout << "Try:\n"; // for(int i = 0; i < N; i++) cout << S[i]; // cout << '\n'; // for(int i = 0; i < N; i++) temp[i] = 0; // for(int i = 0; i < N; i++) if(S[i] == tryS[i]) temp[tryO[i]] = 1; // for(int i = 0; i < N; i++) if(!temp[i]) return i; // return -1; //} //void answer(int S[], int O[]) //{ // cout << "Answer:\n"; // for(int i = 0; i < N; i++) cout << S[i]; // cout << '\n'; // for(int i = 0; i < N; i++) cout << O[i] << " \n"[i == N]; // return; //} void exploreCave(int n) { N = n; vector <int> V(N); for(int i = 0; i < N; i++) V[i] = i; for(int i = 0; i < N; i++) O[i] = -1; auto Try = [&](int l, int r, bool state) { for(int i = 0; i < N; i++) T[i] = !state; for(int i = l; i <= r; i++) T[i] = state; for(int i = 0; i < N; i++) { if(O[i] < 0) continue; T[i] = S[i]; } int ret = tryCombination(T); if(ret < 0) return N; return ret; }; for(int i = 0; i < N; i++) { // cout << i << ":\n"; // for(int x : V) cout << x << ' '; // cout << '\n'; int ret, l = 0, r = V.size() - 1, s; bool state = Try(0, N - 1, 1) > i; while(l <= r) { s = (l + r) >> 1; if(Try(V[0], V[s], state) <= i) l = s + 1; else { r = s - 1; ret = V[s]; } } S[ret] = state; O[ret] = i; for(int j = 0; j < V.size(); j++) if(V[j] == ret) V.erase(V.begin() + j); } return answer(S, O); } //int main() //{ // int n; // cin >> n; // for(int i = 0; i < n; i++) cin >> tryS[i]; // for(int i = 0; i < n; i++) cin >> tryO[i]; // exploreCave(n); // return 0; //}
#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...