Submission #249585

#	Time	Username	Problem	Language	Result	Execution time	Memory
249585		kostia244	The Big Prize (IOI17_prize)	C++17	95.60 / 100	76 ms	5764 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using vi = vector<int>;
map<int, vector<int>> memo;
vector<int> fffff(int p) {
	if(memo.count(p)) return memo[p];
	return memo[p] = ask(p);
}
#define ask fffff
int cb = 1<<30, cg;
vector<int> cnt(20, 0);
vi findgood(vi vals, int cl, int cc, int cr, int _Dep = 0) {
	if(vals.empty() || !cc) return {};
	if(vals.size() == cc) return vals;
	int l = vals.size()/2;
	int r = l+1, go = -1;
	cnt[_Dep]++;
	//for(auto i : vals) cout << i << " "; cout << cl << " " << cc << " " << cr << "::" << endl;
	vi gg, t;
	while(l >= 0 || r < vals.size()) {
		if(l >= 0) {
			t = ask(vals[l]);
			if(t[0] + t[1] == cg) {
				go = l;
				break;
			}
			gg.push_back(vals[l--]);
		}
		if(r < vals.size()) {
			t = ask(vals[r]);
			if(t[0] + t[1] == cg) {
				go = r;
				break;
			}
			gg.push_back(vals[r++]);
		}
	}
	if(l < 0 && r >= vals.size()) return gg;
	vi vl, vr;
	for(int i = 0; i < vals.size(); i++) {
		if(i == go) continue;
		if(i <= l) vl.push_back(vals[i]);
		if(i >= r) vr.push_back(vals[i]);
	}
	t[0] -= cl;
	t[1] -= cr;
	//cout << vals.size() << " to " << vl.size() << " + " << vr.size() << " " << _Dep << " " << cl << " / " << cc << " / " << cr << endl;
	//cout << cl << " " << cc << " " << cr << " " << gg.size()+vl.size()+vr.size() << " " << vals.size() << endl;
	for(auto &i : findgood(vl, cl, t[0], cr+t[1], _Dep+1)) gg.push_back(i);
	for(auto &i : findgood(vr, cl+t[0], t[1], cr, _Dep+1)) gg.push_back(i);
	return gg;
}
int solve(vector<int> p) {
	vi g, pg;
	for(int i = 0; i < min((int)p.size(), 500); i++) {
		vi t = ask(p[i]);
		cb = min(cb, (int)p.size() - t[0] - t[1]);
	}
	cg = p.size() - cb;
	p = findgood(p, 0, cg , 0);
	//for(auto i : p) cout << i << " is good.\n";
	//for(auto i : cnt) cout << i << " ";cout << endl;
	for(auto i : p) {
		std::vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
	}
}
int find_best(int n) {
	vi t;
	for(int i = 0; i < n; i++) t.push_back(i);
	return solve(t);
}

Compilation message (stderr)

prize.cpp: In function 'vi findgood(vi, int, int, int, int)':
prize.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vals.size() == cc) return vals;
     ~~~~~~~~~~~~^~~~~
prize.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l >= 0 || r < vals.size()) {
                  ~~^~~~~~~~~~~~~
prize.cpp:31:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r < vals.size()) {
      ~~^~~~~~~~~~~~~
prize.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l < 0 && r >= vals.size()) return gg;
              ~~^~~~~~~~~~~~~~
prize.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vals.size(); i++) {
                 ~~^~~~~~~~~~~~~
prize.cpp: In function 'int solve(std::vector<int>)':
prize.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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