Submission #585314

#	Time	Username	Problem	Language	Result	Execution time	Memory
585314		Vanilla	The Big Prize (IOI17_prize)	C++17	0 / 100	1 ms	296 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int nr[] = {1, 2, 5, 26, 677};
int vmx = 0, vpos = 0;
const int bp = 1;
const int bp2 = 20;

int getpos (int l, int r) {
	int mid = (l + r) / 2;
	for (int i = 0; i <= mid; i++){
		if (mid + i <= r) {
			vector <int> q = ask(mid + i);
			if (q[0] + q[1] == vmx) return mid + i;
		}
		else if (mid - i >= l) {
			vector <int> q = ask(mid - i);
			if (q[0] + q[1] == vmx) return mid - i;
		}
	}
	assert(0);
}

int brute(int l, int r) {
	for (int i = l; i <= r ; i++){
		vector <int> q = ask(i);
		if (q[0] + q[1] == 0) return i;
	}
	return -1;
}

int solve (int l, int r, int ps) { // assume ps is vmx
	vector <int> q = ask(ps);
	if (q[0] <= bp && ps - l <= bp2) {
		int k = brute(l, ps - 1);
		return (k == -1 ? solve(ps + 1, r, getpos(ps + 1, r)) : k);
	} 
	if (q[1] <= bp && r - ps <= bp2) {
		int k = brute(ps + 1, r);
		return (k == -1 ? solve(l, ps - 1, getpos(l, ps - 1)) : k);
	}
	return max(solve(l, ps - 1, getpos(l, ps - 1)), solve(ps + 1, r, getpos(ps + 1, r)));

}

int find_best(int n) {
	for (int i = 0; i < min(50, n); i++){
		vector <int> k = ask(i);
		if (k[0] + k[1] > vmx) {
			vpos = i;
			vmx = k[0] + k[1]; 
		}
	}
	return solve(1, n, vpos);
	// return solve(1, n, 6);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80