Submission #122665

#	Time	Username	Problem	Language	Result	Execution time	Memory
122665		SirCeness	The Big Prize (IOI17_prize)	C++14	0 / 100	5 ms	2168 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, int tane){
	//cout << "f(" << l << ", " << r << ", " << tane << ")" << endl;
	if (tane <= 0) return;
	if (l > r) return;
	if (l == r){
		if (tane == 0) return;
		vector<int> ans = ask(l);
		vec.pb(mp(arr[l], mp(ans[0], ans[1])));
	}
	int m = (l+r)/2;
	vector<int> ans = ask(arr[r]);
	while (ans[0] + ans[1] != maxx && m < r){
		vec.pb(mp(arr[r], mp(ans[0], ans[1])));
		r--;
		ans = ask(arr[r]);
	}
	int msol = m-1;
	vector<int> ans2 = ask(m);
	while (ans[0] + ans[1] != maxx && m < r) {
		vec.pb(mp(arr[m], mp(ans2[0], ans2[1])));
		m++;
		ans2 = ask(arr[m]);
	}
	f(m+1, r-1, ans2[1] - ans[1]);
	f(l, msol, tane - ans2[1] + ans[1]);
}

int find_best(int size){
	n = size;
	for (int i = 0; i < size; i++) arr[i] = i;
	
	maxx = 0;
	for (int i = 0; i < min(10, n); i++){
		vector<int> ans = ask(i);
		maxx = max(ans[0] + ans[1], maxx);
	}
	
	//cout << "maxx: " << maxx << endl;
	
	int l = 0;
	int r = n-1;
	vector<int> ans1 = ask(l);
	vector<int> ans2 = ask(r);
	while (ans1[0] + ans1[1] != maxx){
		vec.pb(mp(l, mp(ans1[0], ans1[1])));
		l++;
		ans1 = ask(l);
	}
	while (ans2[0] + ans2[1] != maxx){
		vec.pb(mp(r, mp(ans2[0], ans2[1])));
		r--;
		ans2 = ask(r);
	}
	f(l+1, r-1, ans2[0] - ans1[0]);
	
	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:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++){
                  ~~^~~~~~~~~~~~

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