Submission #1226149

#TimeUsernameProblemLanguageResultExecution timeMemory
1226149poatMinerals (JOI19_minerals)C++17
85 / 100
27 ms3784 KiB
#include <bits/stdc++.h> #include "minerals.h" // #include "grader.cpp" using namespace std; mt19937 rng(time(0)); void solve(vector<int> A, vector<int> B, bool fl) { if(A.size() != B.size()) { cout << "DAUN\n"; exit(0); } // for(auto i : A) // cout << i << ' '; // cout << '\n'; // for(auto i : B) // cout << i << ' '; // cout << "\n\n"; if(A.empty()) return; if(A.size() == 1) { Answer(A[0], B[0]); return; } vector<int> a1, b1, a2, b2; for(int i = 0; i < A.size() / 2; i++) a1.push_back(A[i]); for(int i = A.size() / 2; i < A.size(); i++) a2.push_back(A[i]); int x; for(auto i : a1) x = Query(i); if(fl) { a1.swap(a2); b1.swap(b2); } for(int i = 0; i < B.size(); i++) { if(a1.size() == b1.size()) b2.push_back(B[i]); else if(a2.size() == b2.size()) b1.push_back(B[i]); else { int y = Query(B[i]); if(y == x) b1.push_back(B[i]); else b2.push_back(B[i]); x = y; } } solve(a1, b1, 1); solve(a2, b2, 0); } void Solve(int N) { vector<int> vec; for(int i = 1; i <= N * 2; i++) vec.push_back(i); shuffle(vec.begin(), vec.end(), rng); int x; vector<int> A, B; for(auto i : vec) { int y = Query(i); if(y == x) B.push_back(i); else A.push_back(i); x = y; } int y = 0; for(int i = 1; i <= 20; i++) { if((1 << i) <= N) y = i; } y = (1 << y); if(y == N) { solve(A, B, 1); return; } vector<int> a1, b1, a2, b2; for(int i = 0; i < N; i++) { if(i < y) a1.push_back(A[i]); else a2.push_back(A[i]); } for(auto i : a2) x = Query(i); for(int i = 0; i < B.size(); i++) { if(a1.size() == b1.size()) b2.push_back(B[i]); else if(a2.size() == b2.size()) b1.push_back(B[i]); else { int y = Query(B[i]); if(y == x) b1.push_back(B[i]); else b2.push_back(B[i]); x = y; } } solve(a1, b1, 1); solve(a2, b2, 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...