Submission #156824

#	Time	Username	Problem	Language	Result	Execution time	Memory
156824		popovicirobert	Minerals (JOI19_minerals)	C++14	40 / 100	31 ms	2412 KiB

minerals

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

using namespace std;

void Solve(int n) {
	vector <int> pos, ok(2 * n);
	int ans = 0, i;
	for(i = 0; i < 2 * n; i++) {
		int cur = Query(i + 1);
		if(cur == ans) {
			pos.push_back(i);
			ok[i] = 1;
		}
		ans = cur;
	}
	for(i = 0; i < 2 * n; i++) {
		Query(i + 1);
	}

	vector <int> sol(2 * n), in(2 * n);
	ans = 0;

	for(int bit = 15; bit >= 0; bit--) {
		if((1 << bit) >= n) continue;
		
		for(i = 0; i < n; i++) {
			if(i & (1 << bit)) {
				if(in[i]) continue;
				ans = Query(pos[i] + 1);
				in[i] = 1;
			}
		}
		for(i = 0; i < 2 * n; i++) {
			if(ok[i] == 0) {
				if(Query(i + 1) == ans) {
					sol[i] ^= (1 << bit);
				}
				Query(i + 1);
			}
		}
		if(bit == 0) break;
		for(i = 0; i < n; i++) {
			if(i & (1 << bit)) {
				if(i & (1 << (bit - 1))) continue;
				Query(pos[i] + 1);
				in[i] = 0;
			}
		}
	}
	
	for(i = 0; i < 2 * n; i++) {
		if(ok[i] == 0) {
			//cerr << i + 1 << " " << sol[i] + 1 << "\n";
			Answer(i + 1, pos[sol[i]] + 1);
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 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