Submission #122681

#	Time	Username	Problem	Language	Result	Execution time	Memory
122681		SirCeness	The Big Prize (IOI17_prize)	C++14	20 / 100	92 ms	1272 KiB

prize

#include <bits/stdc++.h>
 
#define pb push_back
#define mp make_pair
#include "prize.h"
using namespace std;
typedef long long ll;
 
int arr[200005];
int n;
int tmp[200005];
int maxx;
// 22
 
 
vector<pair<int, pair<int, int> > > vec;
 
 
void f(int l, int r){
	//cout << "f(" << l << ", " << r << ")" << endl;
	if (l > r) return;
	if (l == r){
		vector<int> ans = ask(arr[l]);
		if (ans[0] + ans[1] != maxx) vec.pb(mp(arr[l], mp(ans[0], ans[1])));
		return;
	}
	vector<int> ans1 = ask(arr[l]);
	while (ans1[0] + ans1[1] != maxx && l < r){
		vec.pb(mp(arr[l], mp(ans1[0], ans1[1])));
		l++;
		ans1 = ask(arr[l]);
	}
	
	vector<int> ans2 = ask(arr[r]);
	while (ans2[0] + ans2[1] != maxx && l < r){
		vec.pb(mp(arr[r], mp(ans2[0], ans2[1])));
		r--;
		ans2 = ask(arr[r]);
	}
	
	if (ans1[0] + ans1[1] != maxx){
		vec.pb(mp(arr[l], mp(ans1[0], ans1[1])));
		l++;
	}
	
	if (ans2[0] + ans2[1] != maxx){
		vec.pb(mp(arr[r], mp(ans2[0], ans2[1])));
		r--;
	}
	
	if (ans1[0] == ans2[0]) return;
	
	int m = (l+r)/2;
	f(l+1, m);
	f(m+1, r-1);
}
 
int find_best(int size){
	n = size;
	for (int i = 0; i < size; i++) arr[i] = i;
	
	srand(time(0));
	maxx = 0;
	for (int i = 0; i < 100; i++){
		vector<int> ans = ask(rand()%n);
		maxx = max(ans[0] + ans[1], maxx);
	}
	
	//cout << "maxx: " << maxx << endl;
	
	f(0, n-1);
	
	//cout << "size: " << vec.size() << endl;
	for (int i = 0; i < vec.size(); i++){
		if (vec[i].second.first + vec[i].second.second == 0) return vec[i].first;
	}
	
	assert(0);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++){
                  ~~^~~~~~~~~~~~

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