제출 #944352

#제출 시각아이디문제언어결과실행 시간메모리
944352wii동굴 (IOI13_cave)C++17
100 / 100
317 ms872 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; int tryCombination(int S[]); void answer(int S[], int D[]); void exploreCave(int N); const int MaxN = 5e3; int S[MaxN], D[MaxN]; int knownD[MaxN], knownS[MaxN], mark[MaxN]; void exploreCave(int N) { vector<int> pos; for (int i = 0; i < N; ++i) pos.push_back(i); function<int(int, int)> setup = [&](int u, int mid) { for (int i = 0; i < N; ++i) S[i] = !knownS[u]; for (int i = 0; i <= mid; ++i) S[i] = knownS[u]; for (int i = 0; i < u; ++i) S[knownD[i]] = knownS[i]; return tryCombination(S); }; function<void(int)> query = [&](int u) { int l = 0, r = N - u - 1; knownS[u] = 0; int p = setup(u, -1); knownS[u] = p == -1 || p > u; while (l <= r) { int mid = (l + r) >> 1; //cout << " -> " << l << " " << r << " = " << mid << endl; int res = setup(u, pos[mid]); if (res == -1 || res > u) r = mid - 1; else l = mid + 1; } ++r; //cout << u << " " << pos[r] << endl; knownD[u] = pos[r]; pos.erase(pos.begin() + r); }; for (int i = 0; i < N; ++i) query(i); for (int i = 0; i < N; ++i) S[knownD[i]] = knownS[i]; for (int i = 0; i < N; ++i) D[knownD[i]] = i; answer(S, D); }
#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...