Submission #816145

#	Time	Username	Problem	Language	Result	Execution time	Memory
816145		ono_de206	The Big Prize (IOI17_prize)	C++14	90 / 100	68 ms	1920 KiB

prize

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 2e5 + 10;
pair<int, int> did[mxn];
int mx;

pair<int, int> get(int i) {
	if(did[i].ff != -1) return did[i];
	auto sus = ask(i);
	return did[i] = {sus[0], sus[1]};
}

int solve(int l, int r) {
	if(l == r) {
		get(l);
		if(did[l].ff + did[l].ss == 0) return l;
		return -1;
	}
	int m = (l + r) / 2;
	int l1 = l, r1 = m, l2 = m + 1, r2 = r;
	while(r1 > l1) {
		get(r1);
		if(did[r1].ff + did[r1].ss == 0) return r1;
		else if(did[r1].ff + did[r1].ss < mx) r1--;
		else break;
	}
	while(l2 < r2) {
		get(l2);
		if(did[l2].ff + did[l2].ss == 0) return l2;
		else if(did[l2].ff + did[l2].ss < mx) l2++;
		else break;
	}
	int gg = (did[l1].ff == did[r1].ff && did[l1].ss == did[r1].ss ? -1 : solve(l1, r1));
	if(gg == -1 && did[l2].ff != did[r2].ff && did[l2].ss != did[r2].ss) gg = solve(l2, r2);
	return gg;
}

int find_best(int n) {
	for(int i = 0; i < n; i++) {
		did[i] = {-1, -1};
	}
	if(n <= 5000) {
		for(int i = 0; i < n; i++) {
			get(i);
			if(did[i].ff + did[i].ss == 0) return i;
		}
		return -69;
	}
	int l = 0, r = n - 1;

	for(int i = 0; i < 478; i++) {
		get(i);
		if(did[i].ff + did[i].ss > mx) {
			mx = did[i].ff + did[i].ss;
			l = i;
		} else if(did[i].ff + did[i].ss == 0) {
			return i;
		}
	}
	while(r > l) {
		get(r);
		if(did[r].ff + did[r].ss == 0) return r;
		else if(did[r].ff + did[r].ss < mx) r--;
		else break;
	}
	return solve(l, r);
}

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