# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
950605 | pcc | Minerals (JOI19_minerals) | C++17 | 807 ms | 5872 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
/*
int v = Query(1);
Answer(i, 2 * N + 1 - i);
*/
#define pii pair<int,int>
#define fs first
#define sc second
const int B = 15;
const int mxn = 86011;
vector<pii> req[B];
vector<int> v[2];
int pl,pr;
vector<vector<int>> bk[B];
vector<pii> ans;
int before[mxn];
void Solve(int N) {
vector<int> vv;
for(int i = 1;i<=N*2;i++)vv.push_back(i);
srand(time(NULL));
random_shuffle(vv.begin(),vv.end());
int pre = 0;
for(auto &i:vv){
int tmp = Query(i);
if(tmp==pre){
v[1].push_back(i);
pre = Query(i);
}
else pre = tmp,v[0].push_back(i);
before[i] = pre;
}
assert(v[0].size() == v[1].size());
req[0].push_back(pii(0,N-1));
bk[0].push_back({});
for(int i = 0;i<v[1].size();i++)bk[0].back().push_back(v[1][i]);
pl = 0,pr = v[0].size()-1;
for(int i = 0;i<B;i++){
int cnt = 0;
if(req[i].empty())continue;
while(pl>0){
pre = Query(v[0][--pl]);
}
while(pr>0){
pre = Query(v[0][pr--]);
}
cerr<<i<<endl;
for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
for(auto &j:bk[i]){for(auto &l:j)cerr<<l<<' ';cerr<<",";}cerr<<endl;
assert(req[i].size() == bk[i].size());
for(int j = 0;j<req[i].size();j++){
auto [l,r] = req[i][j];
if(l == r){
ans.push_back(pii(bk[i][j][0],v[0][l]));
continue;
}
int mid = (l+r)>>1;
bk[i+1].push_back({});
bk[i+1].push_back({});
while(pr<mid){
pre = Query(v[0][++pr]);
}
cerr<<pl<<','<<pr<<":"<<pre<<endl;
req[i+1].push_back(pii(l,mid));
req[i+1].push_back(pii(mid+1,r));
for(auto &m:bk[i][j]){
if(before[m]<=before[v[0][mid]]){
bk[i+1].end()[-2].push_back(m);
continue;
}
auto tmp = Query(m);
if(pre == tmp)bk[i+1].end()[-2].push_back(m);
else bk[i+1].end()[-1].push_back(m);
pre = Query(m);
}
}
}
for(auto &i:ans)Answer(i.fs,i.sc);
return;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |