Submission #782414

#	Time	Username	Problem	Language	Result	Execution time	Memory
782414		GusterGoose27	The Big Prize (IOI17_prize)	C++17	100 / 100	43 ms	1696 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

int range[5];

int s = -1;
// vector<int> big;
map<int, vector<int>> cache;

vector<int> get(int i) {
	if (cache.find(i) == cache.end()) cache[i] = ask(i);
	return cache[i];
}

int ans;

bool find(vector<int> &cur, vector<int> &nxt, int l, int r, int num_big, int lf = 0, int rf = 0) { // there are at least num_big big things
	if (l > r) return 1;
	if (num_big == r-l+1) return 1;
	if (l == r) {
		nxt.push_back(cur[l]);
		return 1;
	}
	int mid = (l+r)/2;
	int lq = mid;
	int numl, numr;
	while (lq >= l) {
		vector<int> res = get(cur[lq]);
		if (res[0] == 0 && res[1] == 0) {
			ans = cur[lq];
			return 1;
		}
		if (res[0]+res[1] < s) {
			nxt.push_back(cur[lq]);
			lq--;
			continue;
		}
		else if (res[0]+res[1] == s) {
			// big.push_back(cur[lq]);
			numl = res[0]-lf;
			numr = res[1]-rf-mid+lq;
			break;
		} else { // need to reset
			nxt.clear();
			// big.clear();
			s = res[0]+res[1];
			return 0;			
		}
	}
	if (lq == l-1) {
		if (!find(cur, nxt, mid+1, r, num_big, lf+mid-lq, rf)) return 0;
	}
	else {
		if (!find(cur, nxt, l, lq-1, lq-l-numl, lf, rf+numr+mid-lq)) return 0;
		if (!find(cur, nxt, mid+1, r, r-mid-numr, lf+numl+mid-lq, rf)) return 0;
	}
	return 1;
}

int solve(vector<int> &pos) {
	if (pos.size() == 1) return pos[0];
	vector<int> npos;
	s = -1;
	bool b;
	ans = -1;
	do {
		b = find(pos, npos, 0, pos.size()-1, 0);
	} while (!b);
	if (ans != -1) return ans;
	sort(npos.begin(), npos.end());
	return solve(npos);
}

int find_best(int n) {
	// range[0] = 1;
	// range[1] = 2;
	// range[2] = 5;
	// range[3] = 26;
	// range[4] = 677;
	vector<int> pos(n);
	iota(pos.begin(), pos.end(), 0);
	return solve(pos);
}

Compilation message (stderr)

prize.cpp: In function 'bool find(std::vector<int>&, std::vector<int>&, int, int, int, int, int)':
prize.cpp:57:49: warning: 'numr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |   if (!find(cur, nxt, l, lq-1, lq-l-numl, lf, rf+numr+mid-lq)) return 0;
      |                                               ~~^~~~~
prize.cpp:57:12: warning: 'numl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |   if (!find(cur, nxt, l, lq-1, lq-l-numl, lf, rf+numr+mid-lq)) return 0;
      |        ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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