#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*379/1000);
int m1=max(1,n*614/1000);
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
*/
Compilation message
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:97:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if(a.size()==n){
| ~~~~~~~~^~~
/usr/bin/ld: /tmp/ccfD20JW.o: in function `Query(int)':
grader.cpp:(.text+0x30): multiple definition of `Query(int)'; /tmp/ccgwgJRS.o:minerals.cpp:(.text+0x30): first defined here
/usr/bin/ld: /tmp/ccfD20JW.o: in function `Answer(int, int)':
grader.cpp:(.text+0x100): multiple definition of `Answer(int, int)'; /tmp/ccgwgJRS.o:minerals.cpp:(.text+0x100): first defined here
/usr/bin/ld: /tmp/ccfD20JW.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgwgJRS.o:minerals.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
