Submission #585320

#	Time	Username	Problem	Language	Result	Execution time	Memory
585320		Vanilla	The Big Prize (IOI17_prize)	C++17	20 / 100	77 ms	336 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 = 10;
const int bp2 = 50;

int getpos (int l, int r) {
	int mid = (l + r) / 2;
	for (int i = 0; i <= mid + 2; i++){
		if (mid + i <= r) {
			vector <int> q = ask(mid + i);
			if (q[0] + q[1] == vmx || q[0] + q[1] == 0) return mid + i;
		}
		if (mid - i >= l) {
			vector <int> q = ask(mid - i);
			if (q[0] + q[1] == vmx || q[0] + q[1] == 0) 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) {
	vector <int> q = ask(ps);
	if (q[0] + q[1] == 0) return ps;
	if (l >= r) return -1;
	if (q[0] && 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] && q[1] <= bp && r - ps <= bp2) {
		int k = brute(ps + 1, r);
		return (k == -1 ? solve(l, ps - 1, getpos(l, ps - 1)) : k);
	}
	int p1 = q[0] ? solve(l, ps - 1, getpos(l, ps - 1)) : -1;
	int p2 = q[1] ? solve(ps + 1, r, getpos(ps + 1, r)) : -1;
	return max(p1, p2);

}

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(0, n - 1, vpos);
	// vmx = 1;
	// return solve(0, n-1, 3);
}

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