#include <bits/stdc++.h>
#include "minerals.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
/* Mineral:
i can only figure out that merge sort might be a useful idea
but it is 3/2 * n * log(n) = 1.5 * 43000 * 15 = 2.25 * 43000 = oh wow, i can't math
so the first thing is to find out n minerals which satisfies that no two minerals share the same type
which can be done in n steps
after that, we can merge sort it
let the two parts be X, Y, both have size n
1. put the first n/2 numbers in x to set
2. put every numbers in Y to set, check the answer being changed
3. for every numbers in Y which not causes the answer changed, pop out it from the set
4. go to the next two parts
it's 2*n?
no, for the next level, for one part we can see it as we have done the first step to Y
and for another we just think it the same
so let's go!!
3/2 * 43000 * 15 = 967500
1031500
the recursive function might code in this way:
f(X,Y,flag)
which flag = 0 -> we should do the first step
flag = 1 -> we shouldn't do
and oh, to find out if the correspond is in the first step
we can check if Query() is same to the original answer
done!
*/
int ans=0;
void f(vector<int>& x,vector<int>& y,int flag){
int n=x.size();
shuffle(x.begin(),x.end(),rnd);
shuffle(y.begin(),y.end(),rnd);
if(n==1){
Answer(x[0],y[0]);
return;
}
vector<int> a,b,c,d;
int p=n/2,q=n-p;
for(int i=0;i<n/2;i++){
ans=Query(x[i]);
}
for(int i=0;i<n/2;i++){
a.push_back(x[i]);
}
for(int i=n/2;i<n;i++){
b.push_back(x[i]);
}
for(int i=0;i<n;i++){
if(p==0){
q--;
d.push_back(y[i]);
continue;
}
if(q==0){
p--;
c.push_back(y[i]);
continue;
}
int e=Query(y[i]);
if((e==ans) xor flag){
c.push_back(y[i]);
p--;
}
else{
d.push_back(y[i]);
q--;
}
ans=e;
}
f(a,c,flag^1);
f(b,d,flag);
}
mt19937 rnd(time(NULL));
void Solve(int n){
vector<int> x,y;
for(int i=1;i<=2*n;i++){
int z=Query(i);
if(ans!=z){
x.push_back(i);
}
else{
y.push_back(i);
}
ans=z;
}
shuffle(x.begin(),x.end(),rnd);
shuffle(y.begin(),y.end(),rnd);
f(x,y,1);
}
Compilation message
minerals.cpp: In function 'void f(std::vector<int>&, std::vector<int>&, int)':
minerals.cpp:50:28: error: 'rnd' was not declared in this scope; did you mean 'rand'?
50 | shuffle(x.begin(),x.end(),rnd);
| ^~~
| rand
