제출 #502708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502708		sidon	Minerals (JOI19_minerals)	C++17	90 / 100	59 ms	3396 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;
	if(l < m-1 && m - l + 2 == r - m) --m;
	if(l < m-1 && m - l + 3 == 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) {
 
	array<int, 2> s[N+N];
	for(unsigned int i = 0, j = 12345; int(i) < N + N; ++i)
		s[i] = {int((j *= 3) >> 1), int(i)+1};
	sort(s, s+N+N);
 
	vector<int> b;
 
	for(auto &[_, i] : s) {
		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