Submission #249634

#	Time	Username	Problem	Language	Result	Execution time	Memory
249634		kostia244	The Big Prize (IOI17_prize)	C++17	100 / 100	94 ms	5744 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;
int qry = 0;
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 findbad(int l, int r) {
	if(r-l < 50) {
		int ans = 0;
		while(l < r) {
			ans = max(ans, ask(l)[0] + ask(l)[1]);
			l++;
		}
		return ans;
	}
	int mid = (l+r)/2;
	if(ask(mid)[0] < ask(mid)[1] && l < mid) return findbad(l, mid);
	else return findbad(mid, r);
}
int solve(vector<int> p) {
	vi g, pg;
	if(p.size() > 1000) { 
		cg = findbad(0, p.size());
		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:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vals.size() == cc) return vals;
     ~~~~~~~~~~~~^~~~~
prize.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l >= 0 || r < vals.size()) {
                  ~~^~~~~~~~~~~~~
prize.cpp:32:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r < vals.size()) {
      ~~^~~~~~~~~~~~~
prize.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l < 0 && r >= vals.size()) return gg;
              ~~^~~~~~~~~~~~~~
prize.cpp:43: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:82:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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