Submission #977393

#	Time	Username	Problem	Language	Result	Execution time	Memory
977393		mariaclara	The Big Prize (IOI17_prize)	C++17	90 / 100	55 ms	2388 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int lolipop;
vector<pii> resp;

int a(int x) {
	if(resp[x].fr != -1) return resp[x].fr;
	vector<int> aux = ask(x);
	resp[x] = {aux[0], aux[1]};
	return resp[x].fr;
}

int b(int x) {
	if(resp[x].sc != -1) return resp[x].sc;
	vector<int> aux = ask(x);
	resp[x] = {aux[0], aux[1]};
	return resp[x].sc;
}

int query(int l, int r) {
	while(l < r and a(l) + b(l) != lolipop) {
		if(a(l) + b(l) == 0) return l;
		l++;
	}

	while(l < r and a(r) + b(r) != lolipop) {
		if(a(r) + b(r) == 0) return r;
		r--;
	}

	if(l > r or a(l) == a(r)) return -1; // checo se o intervalo é valido e se existe um valor diferente de lolipop nele

	int mid = (l+r)/2;
	return max(query(l,mid), query(mid+1,r));
}
int find_best(int n) {
	resp.resize(n, mk(-1,-1));

	for(int i = 0; i < min(500,n); i++) lolipop = max(lolipop, a(i) + b(i));

	return query(0, n-1);
}

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