oj.uz

Submission #122665

# Submission time Handle Problem Language Result Execution time Memory
122665 2019-06-29T06:15:09 Z SirCeness The Big Prize (IOI17_prize) C++14
0 / 100
 5 ms 2168 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1184 KB Output is correct
2 Correct 3 ms 1164 KB Output is correct
3 Runtime error 4 ms 2120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1292 KB Output is correct
2 Correct 2 ms 1084 KB Output is correct
3 Runtime error 5 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -