Submission #1170096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170096		wojtup	Minerals (JOI19_minerals)	C++20	31 / 100	8 ms	1000 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 86007;
bool zrobione[MAX];
bool wziete[MAX];

int query2(int x)
{
	wziete[x] = !wziete[x];
	return Query(x);
}

int ustaw_wzorek(vector<int>& prawe, int bit)
{
	int ile = 0;
	for (int i = 0; i < prawe.size(); i++) {
		bool b = ((i&(1<<bit)) != 0);
		if (b != wziete[prawe[i]])
			ile = query2(prawe[i]);
	}
	return ile;
}

int para[MAX];
void zrob(int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) / 2;

	// sprawdz ktore mamy zrobic
	vector<int> gity;
	vector<int> poprawo;
	int ile = 0;
	for (int i = mid+1; i <= r; i++)
		if (!zrobione[i]) {
			poprawo.push_back(i);
			ile = query2(i);
		}
	for (int i = l; i <= mid; i++) {
		if (zrobione[i])
			continue;
		int nowe = query2(i);
		if (nowe == ile)
			gity.push_back(i);
		query2(i);
	}

	int gowno = 0;
	while ((1<<gowno) < poprawo.size())
		gowno++;

	if (gity.empty())
		goto skip;

	for (int bit = 0; bit < gowno; bit++) {
		ile = ustaw_wzorek(poprawo, bit);
		for (int x : gity) {
			int nowe = query2(x);
			if (nowe == ile)
				para[x] |= (1<<bit);
			query2(x);
		}
	}
	for (int x : gity) {
		int ktore = poprawo[para[x]];
		Answer(x, ktore);
		zrobione[x] = true;
		zrobione[ktore] = true;
	}

	skip:
	for (int i = l; i <= r; i++)
		if (wziete[i])
			query2(i);
	zrob(l, mid);
	zrob(mid+1, r);
}

void Solve(int n)
{
	zrob(1, 2*n);
}

/*int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		int x, y;
		cin >> x >> y;
		counterpart[x] = y;
		counterpart[y] = x;
	}
	Solve(N);
	if (num_answers != N) {
		WrongAnswer(6);
	}
	cout << "Accepted: " << num_queries << '\n';
	return 0;
}*/
/*
4
1 5
2 6
3 4
7 8
*/

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10