Submission #120719

#	Time	Username	Problem	Language	Result	Execution time	Memory
120719		youngyojun	Minerals (JOI19_minerals)	C++14	100 / 100	598 ms	5008 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
mt19937 mtrd(time(0));

const int MAXN = 43055;

int __bf;
bool ask(int v) {
	int t = Query(v);
	bool ret = __bf != t;
	__bf = t;
	return ret;
}

int D[MAXN], OP[MAXN];

void f(vector<int> A, vector<int> B, bool flag) {
	int N = sz(A);
	if(!N) return;
	if(1 == N) {
		Answer(A[0], B[0]);
		return;
	}
	shuffle(allv(A), mtrd);
	shuffle(allv(B), mtrd);

	int M = OP[N];
	vector<int> AL, AR, BL, BR;
	for(int i = 0; i < M; i++) {
		AL.eb(A[i]);
		ask(A[i]);
	}
	for(int i = M; i < N; i++) AR.eb(A[i]);

	int oi = 0;
	for(int i; sz(BL) < M && sz(BR) < N-M && oi < N; oi++) {
		i = B[oi];
		((flag ^ ask(i)) ? BR : BL).eb(i);
	}
	for(; oi < N; oi++) (sz(BL) == M ? BR : BL).eb(B[oi]);

	f(AL, BL, !flag);
	f(AR, BR, flag);
}

void precal() {
	D[1] = 0;
	D[2] = 2; OP[2] = 1;
	for(int i = 3; i <= 43000; i++) {
		D[i] = INF; OP[i] = -1;
		for(int j = 1; j*2 <= i; j++) {
			int t = D[j] + D[i-j] + (i+j-1);
			if(D[i] <= t) continue;
			D[i] = t;
			OP[i] = j;
		}
	}
}

void Solve(int N) {
	precal();

	vector<int> A, B, O;
	for(int i = 1; i <= N*2; i++) O.eb(i);
	shuffle(allv(O), mtrd);

	int oi = 0;
	for(int i; sz(A) < N && oi < N*2; oi++) {
		i = O[oi];
		(ask(i) ? A : B).eb(i);
	}
	for(; oi < N*2; oi++) B.eb(O[oi]);

	f(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