Submission #1317582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317582		nikaa123	The Big Prize (IOI17_prize)	C++20	0 / 100	26 ms	396 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

int smax = 0;
int ans = -1;
int n;

void getans(int l, int r, int lval, int rval) {
	if (ans != -1) return;
	if (l > r) return;
	
	int mid = (l+r)/2;
	vector <int> vmid = ask(mid);
	if (vmid[0] + vmid[1] == 0) {
		ans = mid;
		return;
	}
	if (vmid[0] + vmid[1] == smax) {
		getans(l,mid-1,lval,vmid[1]);
		getans(mid+1,r,vmid[0],rval);
		return;
	}
	int curr = mid+1;
	int curl = mid-1;
	vector <int> resr,resl;


	while (curr <= r) {
		resr = ask(curr);
		if (resr[0] + resr[1] == 0) {
			ans = curr;
			return;
		}
		if (resr[0] + resr[1] == smax) break;
		curr++;
	}

	while (curl >= l) {
		resl = ask(curl);
		if (resl[0] + resl[1] == 0) {
			ans = curl;
			return;
		}
		if (resl[0] + resl[1] == smax) break;
		curl--;
	}

	if (curr <= r) {
		getans(curr, r, resr[0], rval);
	}
	if (curl >= l) {
		getans(l, curl, lval, resl[1]);
	}
}

int find_best(int N) {
	int n = N;
	vector <int> res;
	for(int i = 0; i < min(n,500); i++) {
		res = ask(i);
		smax = max(smax,res[0] + res[1]);
	}
	getans(0,n-1,0,0);
	return ans;
}

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