#include <cstdio> #include <cstdlib> #include <vector> #include <unordered_set> #include <random> #include <chrono> #include "minerals.h" using namespace std; #define DEBUG false mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); vector<bool> in; int cnt = 0; bool call_query(int k) { in[k] = !in[k]; int old_cnt = cnt; cnt = Query(k); if (old_cnt != cnt) return true; else return false; } vector<pair<int, int>> ans; void rec(vector<int> a, vector<int> b) { if (a.size() == 1) { ans.push_back({a[0], b[0]}); return; } int mid = (mt()%2 ? a.size()/2 : (a.size()-1)/2); vector<int> a1, b1, a2, b2; unordered_set<int> s; unordered_set<int> res; for (int i = a.size()-1-mid+1; i < a.size(); i++) { int k = uniform_int_distribution<int>(0, i-1)(mt); if (!s.count(k)) res.insert(k); else res.insert(i); } int a1_cnt = 0, a2_cnt = 0; for (int i = 0; i < a.size(); i++) { if (res.count(i)) { a1.push_back(a[i]); if (in[a[i]]) a1_cnt++; } else { a2.push_back(a[i]); if (in[a[i]]) a2_cnt++; } } if (a1_cnt < a2_cnt) swap(a1, a2); for (int i = 0; i < a1.size(); i++) if (!in[a1[i]]) call_query(a1[i]); for (int i = 0; i < a2.size(); i++) if (in[a2[i]]) call_query(a2[i]); for (int i = 0; i < b.size(); i++) { if (!call_query(b[i])) b1.push_back(b[i]); else b2.push_back(b[i]); } if (mt() % 2) { rec(a1, b1); rec(a2, b2); } else { rec(a2, b2); rec(a1, b1); } } void Solve(int N) { in = vector<bool>(2*N+1); vector<pair<vector<int>, vector<int>>> nodes(1); for (int i = 1; i <= 2*N; i++) { if (call_query(i)) nodes[0].second.push_back(i); else { nodes[0].first.push_back(i); } } rec(nodes[0].first, nodes[0].second); for (auto[a, b] : ans) Answer(a, b); } #if DEBUG constexpr int MAX_N = 43000; constexpr int MAX_CALLS = 1000000; namespace { void WrongAnswer(int code) { printf("Wrong Answer [%d]\n", code); exit(0); } int N; int counterpart[2 * MAX_N + 1]; int num_queries; int num_kinds; int on[2 * MAX_N + 1]; int count[2 * MAX_N + 1]; int num_answers; int answer[2 * MAX_N + 1]; } // namespace int Query(int x) { if (!(1 <= x && x <= 2 * N)) { WrongAnswer(1); } if (++num_queries > MAX_CALLS) { WrongAnswer(2); } const int type = std::min(x, counterpart[x]); if (on[x]) { --on[x]; --count[type]; if (count[type] == 0) { --num_kinds; } } else { ++on[x]; ++count[type]; if (count[type] == 1) { ++num_kinds; } } return num_kinds; } void Answer(int a, int b) { if (++num_answers > N) { WrongAnswer(6); } if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) { WrongAnswer(3); } if (answer[a] != 0) { WrongAnswer(4); } answer[a] = b; if (answer[b] != 0) { WrongAnswer(4); } answer[b] = a; if (!(counterpart[a] == b && counterpart[b] == a)) { WrongAnswer(5); } } int main() { if (scanf("%d", &N) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } for (int i = 1; i <= N; ++i) { int x, y; if (scanf("%d%d", &x, &y) != 2) { fprintf(stderr, "Error while reading input\n"); exit(1); } counterpart[x] = y; counterpart[y] = x; } Solve(N); if (num_answers != N) { WrongAnswer(6); } printf("Accepted: %d\n", num_queries); return 0; } #endif