| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 901556 | Darren0724 | Minerals (JOI19_minerals) | C++17 | 0 ms | 0 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>
#include "grader.cpp"
using namespace std;
mt19937 rnd(time(0));
int last=0;
vector<int> have(100000);
int ask(int k){
have[k] ^= 1;
int p = Query(k);
int tmp = p - last;
last = p;
return tmp;
}
void dc(vector<int> &a,vector<int> &b){
shuffle(a.begin(),a.end(),rnd);
shuffle(b.begin(),b.end(),rnd);
int n=a.size();
if(n==1){
Answer(a[0],b[0]);
return;
}
int m=max(1,n*37/100);
int m1=max(1,n*63/100);
int sz1=0,sz2=0;
vector<int> a1,a2,b1,b2,tmp1,tmp2;
for(int i=0;i<n;i++){
if(have[a[i]]){
sz1++;
}
if(have[b[i]]){
sz2++;
}
}
if(min(abs(m-sz2),abs(m-sz1))>min(abs(m1-sz2),abs(m1-sz1))){
m=m1;
}
if(abs(m-sz2)<abs(m-sz1)){
swap(a,b);
swap(tmp1,tmp2);
swap(sz1,sz2);
}
//cout<<sz1<<' '<<sz2<<' '<<m<<endl;
for(int i=0;i<n;i++){
if(have[a[i]]){
tmp1.push_back(a[i]);
}
else{
tmp2.push_back(a[i]);
}
}
if(sz1>m){
int t=abs(m-sz1);
for(int i=0;i<t;i++){
ask(tmp1[i]);
}
}
else{
int t=abs(m-sz1);
for(int i=0;i<t;i++){
ask(tmp2[i]);
}
}
for(int i=0;i<n;i++){
if(have[a[i]]){
a1.push_back(a[i]);
}
else{
a2.push_back(a[i]);
}
}
int cnt=0;
for(int i=0;i<n;i++){
if(cnt==m){
b2.push_back(b[i]);
continue;
}
if(ask(b[i])==0){
cnt++;
b1.push_back(b[i]);
}
else{
b2.push_back(b[i]);
}
}
dc(a1,b1);
dc(a2,b2);
}
void Solve(int n) {
vector<int> a,b;
vector<int> t(n*2);
iota(t.begin(),t.end(),1);
shuffle(t.begin(),t.end(),rnd);
for(int j=0;j<n*2;j++){
int i=t[j];
if(a.size()==n){
b.push_back(i);
continue;
}
if(ask(i)==0){
b.push_back(i);
}
else{
a.push_back(i);
}
}
dc(a,b);
}
/*
times: N*2 + N log N * 3/2
*/