Submission #502705

#	Time	Username	Problem	Language	Result	Execution time	Memory
502705		sidon	Minerals (JOI19_minerals)	C++17	90 / 100	37 ms	2808 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
 
const int LIM = 43e3;
 
int A[LIM], L, R = -1, last;
 
#define ask(Z) (last = Query(Z))
 
void dfs(int l, int r, vector<int> b, bool on) {
	if(r - l < 1) return;
	if(r - l < 2) return Answer(A[l], b[0]);
 
	int m = (l + r) / 2;
	if(l < m-1 && m - l == r - m) --m;
	if(l < m-1 && m - l + 1 == r - m) --m;
 
	for(int i = l; i < m; ++i)
		ask(A[i]);
 
	vector<int> bL, bR;
 
	for(int &i : b) {
		if((int)size(bL) == m - l) {
			bR.push_back(i);
			continue;
		}
		if((int)size(bR) == r - m) {
			bL.push_back(i);
			continue;
		}
		int prev = last;
		((prev == ask(i)) ^ on ? bL : bR).push_back(i);
	}
 
	dfs(l, m, bL, on ^ 1);
	dfs(m, r, bR, on);
}
 
void Solve(int N) {
 	vector<int> b;
 
	for(int i = 1; i <= N+N; ++i) {
		if(R == N - 1 || ask(i) < R + 2) {
			b.push_back(i);
		} else A[++R] = i;
	}
	dfs(0, N, b, 1);
}

• 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