Submission #1226140

#TimeUsernameProblemLanguageResultExecution timeMemory
1226140poatMinerals (JOI19_minerals)C++17
85 / 100
25 ms3300 KiB
#include <bits/stdc++.h> #include "minerals.h" // #include "grader.cpp" using namespace std; 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) { int q = 0; vector<int> A, B; for(int i = 1; i <= N * 2; i++) { if(Query(i) != q) { A.push_back(i); q++; } else B.push_back(i); } 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]); } int x; 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...