Submission #1180211

#TimeUsernameProblemLanguageResultExecution timeMemory
1180211kunzaZa183Cave (IOI13_cave)C++20
51 / 100
147 ms98444 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { vector<int> left, det; int *corr = new int[N], *linkto = new int[N]; for (int i = 0; i < N; i++) left.push_back(i); for (int i = 0; i < N; i++) { int *qry = new int[N]; fill(qry, qry + N, 0); for (auto a : det) qry[a] = corr[a]; int x = tryCombination(qry); if (x == -1) { x = N; } int pos = -1; if (x > i) { pos = 0; } else pos = 1; int l = 0, r = left.size() - 1; while (l < r) { int mid = (l + r) / 2; for (int i = l; i <= mid; i++) qry[left[i]] = pos; for (int i = mid + 1; i <= r; i++) qry[left[i]] = 1 - pos; x = tryCombination(qry); if (x == -1) { x = N; } if (x > i) { r = mid; } else l = mid + 1; } linkto[left[l]] = i; corr[left[l]] = pos; det.push_back(left[l]); left.erase(left.begin() + l); } answer(corr, linkto); }
#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...