Submission #600302

#	Time	Username	Problem	Language	Result	Execution time	Memory
600302		Jomnoi	The Big Prize (IOI17_prize)	C++17	90 / 100	89 ms	5432 KiB

prize

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

const int MAX_N = 2e5 + 5;

int l, r, mid;
vector <int> result, result2;
vector <int> A[MAX_N];

vector <int> query(int i) {
	if(!A[i].empty()) {
		return A[i];
	}
	return A[i] = ask(i);
}

int find_best(int n) {
	int now = 0;
	for(int i = 0; i < min(n, 500); i++) {
		result = query(i);
		now = max(now, result[0] + result[1]);
	}

	for(int i = 0; i < n; i++) {
		result = query(i);
		if(result[0] + result[1] == 0) {
			return i;
		}
		if(result[0] + result[1] != now) {
			continue;
		}

		l = i, r = n - 1;
		while(l <= r) {
			mid = (l + r) / 2;

			result2 = query(mid);
			if(result == result2) {
				i = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
	}
	return 0;
}

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