Submission #585328

#	Time	Username	Problem	Language	Result	Execution time	Memory
585328		Vanilla	The Big Prize (IOI17_prize)	C++17	0 / 100	91 ms	280 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 = 30;
const int bp2 = 5000000;

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;
		}
	}
	return mid;
	// 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) {
	// cout << l << " " << r << " " << ps << "\n";
	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 rs = -1;
	if (q[0] > q[1]){
		rs = solve(l, ps - 1, getpos(l, ps - 1));
		return (rs == -1 ? solve(ps + 1, r, getpos(ps + 1, r)): rs);
	}
	else {
		rs = solve(ps + 1, r, getpos(ps + 1, r));
		return (rs == -1 ? solve(l, ps - 1, getpos(l, ps - 1)): rs);
	}

}

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) {
			vmx = k[0] + k[1]; 
		}
	}
	// cout << getpos(0, n - 1);
	return solve(0, n - 1, getpos(0, n - 1));
	// vmx = 1;
	// return solve(0, n-1, 3);
}

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