Submission #411236

#	Time	Username	Problem	Language	Result	Execution time	Memory
411236		amoo_safar	Minerals (JOI19_minerals)	C++17	100 / 100	83 ms	3892 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;
}

int norm(vector<int>& A){
	int c0 = 0;
	int c1 = 0;
	int n = A.size();
	for(auto x : A)
		(mk[x] ? c1 : c0) ++;
	return (n / 2) - min(c0, c1);
}

void normalize(vector<int>& A){
	int c0 = 0;
	int c1 = 0;
	int n = A.size();
	for(auto x : A)
		(mk[x] ? c1 : c0) ++;
	int mn = 0, cnt = c0;
	if(c0 > c1) mn = 1, cnt = c1;
	for(auto x : A){
		if(cnt == (n / 2)) break;
		if(mn == mk[x]) continue;
		cnt ++;
		Ask(x);
	}
}

void solve(vector<int> A, vector<int> B){
	assert(A.size() == B.size());
	// random_shuffle(A.begin(), A.end());
	// random_shuffle(B.begin(), B.end());
	int n = A.size();
	if(n == 1){
		Answer(A[0], B[0]);
		return ;
	}
	if(norm(A) > norm(B)) swap(A, B);
	normalize(A);
	sort(A.begin(), A.end(), [&](int i, int j){
		return mk[i] > mk[j];
	});

	int sz = 0;
	for(auto x : A) if(mk[x]) sz ++;

	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: 10 / 10