Submission #1247026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247026		PlayVoltz	Minerals (JOI19_minerals)	C++20	100 / 100	30 ms	4632 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int booga=0, ooga;

bool query(int a){
	ooga=Query(a);
	swap(ooga, booga);
	return (ooga==booga);
}

void dnc(vector<int> a, vector<int> b, bool got){
	if (a.size()==1){
		Answer(a[0], b[0]);
		return;
	}
	int n=a.size(), mid=max(1, got?7*n/10:3*n/10), p=0;
	vector<int> al, bl, ar, br;
	for (int i=0; i<mid; ++i){
		if (!got)query(a[i]);
		al.pb(a[i]);
	}
	for (int i=mid; i<n; ++i){
		if (got)query(a[i]);
		ar.pb(a[i]);
	}
	for (;bl.size()<al.size()&&br.size()<ar.size(); ++p){
		if (query(b[p]))bl.pb(b[p]);
		else br.pb(b[p]);
	}
	while (bl.size()<al.size())bl.pb(b[p]), ++p;
	while (br.size()<ar.size())br.pb(b[p]), ++p;
	dnc(al, bl, 1), dnc(ar, br, 0);
}

void Solve(int n){
	vector<int> a, b;
	for (int i=1; i<=2*n; ++i){
		if (query(i))a.pb(i);
		else b.pb(i);
	}
	dnc(a, b, 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: 10 / 10