Submission #706204

#	Time	Username	Problem	Language	Result	Execution time	Memory
706204		alvingogo	Minerals (JOI19_minerals)	C++14	90 / 100	75 ms	2792 KiB

minerals

#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;

mt19937 rnd(time(NULL));
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);
}
void Solve(int n){
	vector<int> x,y;
	int a=n,b=n;
	for(int i=1;i<=2*n;i++){
		if(a==0){
			y.push_back(i);
			continue;
		}
		int z=Query(i);
		if(ans!=z){
			a--;
			x.push_back(i);
		}
		else{
			b--;
			y.push_back(i);
		}
		ans=z;
	}
	shuffle(x.begin(),x.end(),rnd);
	shuffle(y.begin(),y.end(),rnd);
	f(x,y,1);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10