Submission #1227930

#TimeUsernameProblemLanguageResultExecution timeMemory
1227930lolokaMinerals (JOI19_minerals)C++20
40 / 100
143 ms10416 KiB
#include "minerals.h" #include<bits/stdc++.h> using namespace std; mt19937 rng(time(0)); int kl; void slv(vector<int> v1, vector<int> v2) { /*for(auto i : v1) cout << i << " "; cout << "\n"; for(auto i : v2) cout << i << " "; cout << "\n" << "\n";*/ if((int)v1.size() == 1) { Answer(v1[0], v2[0]); return; } int n = (int)v1.size(); vector<int> l1, l2, r1, r2; for(int i = 0; i < n / 2; i++) l1.push_back(v1[i]); for(int i = n / 2; i < n; i++) r1.push_back(v1[i]); map<int, int> mp; shuffle(v2.begin(), v2.end(), rng); for(int i = 0; i < n; i++) { if(l2.size() == l1.size()) { r2.push_back(v2[i]); continue; } if(r2.size() == r1.size()) { l2.push_back(v2[i]); continue; } int k = Query(v2[i]); //cout << k << " " << kl << " " << v2[i] << " f\n"; if(k == kl) l2.push_back(v2[i]), mp[v2[i]] = 1; else r2.push_back(v2[i]), mp[v2[i]] = 2; kl = k; } int S1 = (int)l1.size(); if(n / 2 > 1) { for(int i = S1 / 2; i < S1; i++) kl = Query(l1[i]); for(auto i : v2) if(mp[i] == 1) kl = Query(i); } slv(l1, l2); swap(r1, r2); if(n - n / 2 > 1) { int S = (int)r1.size(); for(int i = 0; i < S / 2; i++) if(!mp[r1[i]]) kl = Query(r1[i]); for(int i = S / 2; i < S; i++) if(mp[r1[i]]) kl = Query(r1[i]); } slv(r1, r2); } void Solve(int n) { vector<int> v1, v2; map<int, int> mp; kl = 0; for(int i = 1; i <= 2 * n; i++) { if(kl == n) { v2.push_back(i); continue; } int k = Query(i); mp[i] = 1; if(k == kl) v2.push_back(i); else v1.push_back(i); kl = k; } for(int i = 0; i < n / 2; i++) if(!mp[v1[i]]) kl = Query(v1[i]); for(int i = n / 2; i < n; i++) if(mp[v1[i]]) kl = Query(v1[i]); for(auto i : v2) if(mp[i]) kl = Query(i); slv(v1, v2); }
#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...