Submission #416176

#	Time	Username	Problem	Language	Result	Execution time	Memory
416176		InternetPerson10	The Big Prize (IOI17_prize)	C++17	20 / 100	1064 ms	1048580 KiB

prize

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

using namespace std;

int le[200001], ri[200001];
map<int, int> ge;
vector<int> vec;

int bad, unfound = 0;

vector<int> asksk(int n) {
	if(le[n] >= 0) {
		vector<int> v;
		v.push_back(le[n]);
		v.push_back(ri[n]);
		return v;
	}
	else return ask(n);
}

int rec(int l, int r, int u) {
	// cout << l << ' ' << r << ' ' << u << "\n";
	int k = u;
	if(u == 0) return 0;
	int mid = (l+r)/2;
	int l_r, r_l; l_r = r_l = mid;
	while(true) {
		if(l_r == l || u == 0) break;
		auto v = asksk(l_r);
		le[l_r] = v[0]; ri[l_r] = v[1];
		if(le[l_r] + ri[l_r] != bad) u--;
		else {
			u -= rec(l, l_r, le[l_r] - le[l]);
			break;
		}
		l_r--;
	}
	while(true) {
		if(r_l == r || u == 0) break;
		auto v = asksk(r_l);
		le[r_l] = v[0]; ri[r_l] = v[1];
		if(le[r_l] + ri[r_l] != bad && r_l != mid) u--;
		else {
			u -= rec(r_l, r, u - le[r_l] + le[l]);
			break;
		}
		r_l++;
	}
	return k;
}

int find_best(int n) {
	for(int i = 0; i < n; i++) le[i] = ri[i] = -1;
	int k = 0;
	while(k * k / 2 < n) k++;
	for(int i = 0; i < k; i++) {
		auto v = asksk(i);
		le[i] = v[0]; ri[i] = v[1];
		ge[le[i] + ri[i]]++;
	}
	for(auto p : ge) {
		vec.push_back(p.first);
	}
	bad = vec[vec.size() - 1]; // sum of lowest prize
	unfound = bad;
	int st;
	int buffer = 0;
	for(int i = 0; i < k; i++) {
		if(le[i] + ri[i] != bad) {
			buffer++;
		}
		else {
			unfound -= buffer; buffer = 0;
			st = i;
		}
	}
	rec(st, n, unfound);
	for(int i = 0; i < n; i++) {
		if(le[i] + ri[i] == 0) return i;
	}
	return -1;
}
 

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:78:5: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |  rec(st, n, unfound);
      |  ~~~^~~~~~~~~~~~~~~~

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