Submission #123623

#	Time	Username	Problem	Language	Result	Execution time	Memory
123623		Sorting	The Big Prize (IOI17_prize)	C++14	97.69 / 100	66 ms	504 KiB

prize

#include <bits/stdc++.h>

using namespace std;

vector<int> ask(int i);

int mx = 0, idx = 0;

int solve(int l, int r, int cntl, int cntr){
	if(l > r || cntl == cntr){
		return -1;
	}

	int mid = (l + r) >> 1;

	vector<int> a = ask(mid);
	int curr = a[0] + a[1];

	if(curr == 0){
		return mid;
	}
	if(curr < mx){
		int i;

		for(i = mid - 1; i >= l; i--){
			a = ask(i);
			curr = a[0] + a[1];

			if(curr == 0){
				return i;
			}

			if(curr == mx){
				if(rand() % 2){
					int rval = solve(mid + 1, r, a[0] + (mid - i), cntr);

					if(rval != -1){
						return rval;
					}
					return solve(l, i, cntl, a[0]);
				}
				else{
					int rval = solve(l, i, cntl, a[0]);

					if(rval != -1){
						return rval;
					}
					return solve(mid + 1, r, a[0] + (mid - i), cntr);
				}
			}
		}

		return solve(mid + 1, r, cntl + (mid - i), cntr);
	}

	int rval = solve(mid + 1, r, a[0], cntr);

	if(rval != -1){
		return rval;
	}
	return solve(l, mid - 1, cntl, a[0]);
}

int find_best(int n){
	int l = 0, r = n - 1;
	int pr = n;

	for(int i = 0; i < min(n, 472); i++){
		vector<int> a = ask(i);
		int curr = a[0] + a[1];

		if(curr > mx){
			mx = curr;
			idx = i;
		}
	}

	return solve(0, n - 1, 0, mx);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:65:6: warning: unused variable 'l' [-Wunused-variable]
  int l = 0, r = n - 1;
      ^
prize.cpp:65:13: warning: unused variable 'r' [-Wunused-variable]
  int l = 0, r = n - 1;
             ^
prize.cpp:66:6: warning: unused variable 'pr' [-Wunused-variable]
  int pr = n;
      ^~

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