Submission #411084

#	Time	Username	Problem	Language	Result	Execution time	Memory
411084		amoo_safar	Minerals (JOI19_minerals)	C++17	90 / 100	69 ms	3848 KiB

minerals

#include "minerals.h"

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5;

int mk[N];
int la = 0;
bool Ask(int u){
	mk[u] ^= 1;
	int res = Query(u);
	bool ch = la != res;
	la = res;
	return ch;
}

void solve(vector<int> A, vector<int> B){
	assert(A.size() == B.size());
	int n = A.size();
	if(n == 1){
		Answer(A[0], B[0]);
		return ;
	}
	int st = mk[A[0]];
	int sz = 0;
	if(st == 0){
		for(int i = 0; i < n / 2; i++) Ask(A[i]);
		sz = n / 2;
	} else {
		for(int i = 0; i < n / 2; i++) Ask(A[n - 1 - i]);
		sz = (n + 1) / 2;
	}
	vector<int> A2[2], B2[2];
	for(int i = 0; i < sz; i++) A2[0].pb(A[i]);
	for(int i = sz; i < n; i++) A2[1].pb(A[i]);

	for(auto x : B){
		if(A2[0].size() == B2[0].size()){
			B2[1].pb(x);
			continue;
		}
		if(A2[1].size() == B2[1].size()){
			B2[0].pb(x);
			continue;
		}
		bool fl = Ask(x);
		B2[fl ? 1 : 0].pb(x);
	}
	solve(A2[0], B2[0]);
	solve(A2[1], B2[1]);
}

void Solve(int n) {
	vector<int> A, B;
	for(int i = 1; i <= n + n; i++)
		if(Ask(i))
			A.pb(i);
		else
			B.pb(i);
	solve(A, B);
}

• 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