Submission #376066

#	Time	Username	Problem	Language	Result	Execution time	Memory
376066		pit4h	Minerals (JOI19_minerals)	C++14	90 / 100	103 ms	3692 KiB

minerals

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

const int MAXN = 1e5+1;
bool on[MAXN];

int current;
int query(int x) {
	on[x] = !on[x];	
	current = Query(x);
	return current;
}
int levels = 0;
void solve(int n, vi ls, vi rs) {
	if(n==1) {
		Answer(ls[0], rs[0]);
		return;
	}
	random_shuffle(ls.begin(), ls.end());
	random_shuffle(rs.begin(), rs.end());
	vi Ls[2], Rs[2];
	for(int i=0; i<n/2; ++i) {
		query(ls[i]);
		Ls[on[ls[i]]].push_back(ls[i]);
	}
	for(int i=n/2; i<n; ++i) {
		Ls[on[ls[i]]].push_back(ls[i]);
	}
	for(int i=0; i<n; ++i) {
		int old = current;
		if(Rs[0].size() == Ls[0].size()) {
			current = old;
		}
		else if(Rs[1].size() == Ls[1].size()) {
			current--;
		}
		else {
			query(rs[i]);
		}
		if(current == old) {
			Rs[1].push_back(rs[i]);
		}
		else {
			Rs[0].push_back(rs[i]);
		}
	}
	assert(Ls[0].size() == Rs[0].size() && Ls[1].size() == Rs[1].size());

	solve(Ls[0].size(), Ls[0], Rs[0]);
	solve(Ls[1].size(), Ls[1], Rs[1]);
}

void Solve(int N) {
	vi ls={}, rs={};
	int val = 0;
	for(int i=1; i<=2*N; ++i) {
		int nval = query(i);
		if(nval == val) {
			rs.push_back(i);	
		}
		else {
			ls.push_back(i);
		}
		val = nval;
	}
	solve(N, ls, rs);
}

• 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