Submission #334767

#	Time	Username	Problem	Language	Result	Execution time	Memory
334767		LucaDantas	The Big Prize (IOI17_prize)	C++17	20 / 100	97 ms	3680 KiB

prize

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

#define pb push_back
#define sz(a) (int)((a).size())

const vector<int> good = {0, 0};

constexpr int maxn = 2e5;
int base, N;

int solve(vector<int>& v, int l, int r) {
	if(!sz(v)) return -1;
	if(sz(v) == 1) {
		if(ask(v[0]) == good) return v[0];
		return -1;
	}
	// printf("l, r == %d %d %d %d\n", l, r, v[0], v.back());
	// for(int x : v)
	// 	printf("%d ", x);
	// printf("\n");
	int m = sz(v)/2;
	vector<int> a, b;
	for(int i = 0; i < m; i++)
		a.pb(v[i]);
	vector<int> res = ask(v[m]);
	if(res == good) return v[m];
	if(res[0]+res[1] == base) {
		// printf("v %d\n", v[m]);
		for(int i = m; i < sz(v); i++)
			b.pb(v[i]);
		if(res[0] - l) {
			int ans = solve(a, l, res[1]);
			if(ans != -1) return ans;
		}
		if(r - res[1]) {
			int ans = solve(b, res[0], r);
			if(ans != -1) return ans;
		}
	} else {
		int seen = 1, p = v[m]+1;
		bool ok = 0;
		while(p <= v.back()) {
			// printf("p %d\n", p);
			res = ask(p);
			if(res == good) return p;
			if(res[0]+res[1] == base) {
				for(int i = p+1; i <= v.back(); i++)
					b.pb(i);
				if(res[0] - l - seen) {
					int ans = solve(a, l, res[1]+seen);
					if(ans != -1) return ans;
				}
				if(r - res[1]) {
					int ans = solve(b, res[0], r);
					if(ans != -1) return ans;
				}
				ok = 1;
			}
			++p, ++seen;
		}
		if(!ok) {
			int r = seen+(v.back()==N-1?0:(ask(v.back()+1)[1]));
			// if(r + l != base) {
				int ans = solve(a, l, r);
				if(ans != -1) return ans;
			// }
		}
	}
	return -1;
}

int find_best(int n) {
	N = n;
	int last = 0;
	// base = 3;
	for(int i = 0; i < min(475, n); i++) {
		vector<int> opa = ask(i);
		if(opa == good) return i;
		if(opa[0]+opa[1] >= base)
			base = opa[0]+opa[1];
	}
	vector<int> a;
	for(int i = 0; i < n; i++)
		a.pb(i);
	return solve(a, 0, 0);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:76:6: warning: unused variable 'last' [-Wunused-variable]
   76 |  int last = 0;
      |      ^~~~

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