Submission #1248028

#TimeUsernameProblemLanguageResultExecution timeMemory
1248028GrayMinerals (JOI19_minerals)C++20
90 / 100
635 ms12956 KiB
#include "minerals.h" #include <algorithm> #include <bits/stdc++.h> #include <cassert> using namespace std; #define ll long long #define ff first #define ss second #define ln "\n" mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); struct API{ set<ll> ins; ll val, n; vector<ll> perm; API(int N){ val=-1; n=N; for (ll i=0; i<n; i++) perm.push_back(i); shuffle(perm.begin(), perm.end(), rnd); } ll getind(ll ind){ return perm[ind-1]+1; } bool status(ll ind){ ind=getind(ind); return ins.count(ind)>0; } void in(ll ind){ ind=getind(ind); if (ins.count(ind)) return; val=Query(ind); ins.insert(ind); } void out(ll ind){ ind=getind(ind); if (!ins.count(ind)) return; val=Query(ind); ins.erase(ind); } ll get(){ return val; } // void debug(){ // for (auto x:ins) // } }; int n; void Solve(int N) { n=2*N; API com(2*N); vector<ll> a, b; int tmp=-1; for (ll i=1; i<=n; i++){ com.in(i); int ntmp = com.get(); if (ntmp!=tmp){ a.push_back(i); }else{ b.push_back(i); } tmp=ntmp; } vector<pair<vector<ll>, vector<ll>>> search, nsearch; vector<pair<ll, ll>> res; search.push_back({a, b}); while (!search.empty()){ set<ll> swps; for (auto &[sa, sb]:search){ // { // for (auto x:sa) cout << x << " "; // cout << endl; // for (auto x:sb) cout << x << " "; // cout << endl << endl; // } assert(sa.size()==sb.size()); if (sa.size()==1){ res.push_back({com.getind(sa[0]), com.getind(sb[0])}); continue; } ll sz=sa.size(), complex=0, complex2=0; for (ll i=0; i<sz/2; i++){ if (!com.status(sa[i])) complex++; // com.in(sa[i]); } for (ll i=sz/2; i<sz; i++){ if (com.status(sa[i])) complex++; // com.out(sa[i]); } for (ll i=0; i<sz/2; i++){ if (com.status(sa[i])) complex2++; // com.in(sa[i]); } for (ll i=sz/2; i<sz; i++){ if (!com.status(sa[i])) complex2++; // com.out(sa[i]); } if (complex<complex2){ for (ll i=0; i<sz/2; i++){ com.in(sa[i]); } for (ll i=sz/2; i<sz; i++){ com.out(sa[i]); } }else{ for (ll i=0; i<sz/2; i++){ com.out(sa[i]); } for (ll i=sz/2; i<sz; i++){ com.in(sa[i]); } swps.insert(sa[0]); } } nsearch.clear(); for (auto &[sa, sb]:search){ if (sa.size()==1) continue; vector<ll> left1, right1, left2, right2; ll sz=sa.size(); for (ll i=0; i<sz/2; i++){ left1.push_back(sa[i]); } for (ll i=sz/2; i<sz; i++){ right1.push_back(sa[i]); } for (ll i=0; i<(ll)sb.size()-1; i++){ ll x=sb[i]; ll prev=com.get(); if (com.status(x)){ com.out(x); }else{ com.in(x); } ll cur = com.get(); if (prev==cur) { if (swps.count(sa[0])) right2.push_back(x); else left2.push_back(x); } else { if (!swps.count(sa[0])) right2.push_back(x); else left2.push_back(x); } if (left1.size()==left2.size()){ for (ll j=i+1; j<(ll)sb.size()-1; j++) right2.push_back(sb[j]); break; }else if (right1.size()==right2.size()){ for (ll j=i+1; j<(ll)sb.size()-1; j++) left2.push_back(sb[j]); break; } } if (left2.size()<right2.size()) left2.push_back(sb.back()); else right2.push_back(sb.back()); nsearch.push_back({left1, left2}); nsearch.push_back({right1, right2}); } swap(search, nsearch); } for (auto [x, y]:res) Answer(x, y); }
#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...