Submission #816090

#	Time	Username	Problem	Language	Result	Execution time	Memory
816090		ono_de206	The Big Prize (IOI17_prize)	C++14	0 / 100	5 ms	1836 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;
	while(l < m) {
		get(l);
		if(did[l].ff + did[l].ss == 0) return l;
		else if(did[l].ff + did[l].ss < mx) l++;
		else break;
	}
	while(r > m + 1) {
		get(r);
		if(did[r].ff + did[r].ss == 0) return r;
		else if(did[r].ff + did[r].ss < mx) r--;
		else break;
	}
	if(did[l].ff + did[l].ss == mx && did[r].ff + did[r].ss == mx && did[l].ss == did[r].ss) return -1;
	return max(solve(l, m), solve(m + 1, r));
}

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;
		}
	}
	return solve(l, r);
}

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