Submission #615473

#	Time	Username	Problem	Language	Result	Execution time	Memory
615473		valerikk	Minerals (JOI19_minerals)	C++17	100 / 100	56 ms	4240 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 gen(239);

int last;

bool query(int x) {
	int cur = Query(x);
	bool res = cur != last;
	last = cur;
	return res;
}

void solve(vector<int> a, vector<int> b, bool f) {
	int n = a.size();
	if (n == 1) {
		Answer(a[0], b[0]);
		return;
	}
	int m = max(1, n / 3);
	vector<int> a1, a2, b1, b2;
	for (int i = 0; i < m; ++i) {
		query(a[i]);
		a1.push_back(a[i]);
	}
	for (int i = m; i < n; ++i) {
		a2.push_back(a[i]);
	}
	for (int i = 0; i < n; ++i) {
		if (b1.size() == a1.size()) {
			b2.push_back(b[i]);
			continue;
		}
		if (b2.size() == a2.size()) {
			b1.push_back(b[i]);
			continue;
		}
		if (query(b[i]) ^ f) {
			b2.push_back(b[i]);
		} else {
			b1.push_back(b[i]);
		}
	}
	solve(a1, b1, !f);
	solve(a2, b2, f);
}
 
void Solve(int N) {
	vector<int> a, b;
	last = 0;
	for (int i = 1; i <= 2 * N; ++i) {
		if (query(i)) {
			a.push_back(i);
		} else {
			b.push_back(i);
		}
	}
	solve(a, b, true);
}	

• 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