Submission #290746

#	Time	Username	Problem	Language	Result	Execution time	Memory
290746		abyyskit	The Big Prize (IOI17_prize)	C++14	94.92 / 100	68 ms	392 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

int ANS;
int SCORE;
bool DONE;
void findAll(int l, int r, int L, int R){
	//cout << "findALL(" << l << ", " << r << ")\n";
	if (DONE) return;
	if (l == r) return;
	int mid = (l + r)/2;
	vector<int> tmp = ask(mid);
	if (tmp[0] + tmp[1] == 0){
		ANS = mid;
		DONE = true;
		return;
	}
	if (tmp[0] + tmp[1] == SCORE){
		if (tmp[0] - L != 0){
			findAll(l, mid, L, tmp[1]);
		}
		if (R - tmp[1] != 0){
			findAll(mid + 1, r, tmp[0], R);
		}
		return;
	}
	int rp = l;
	int rL;
	int rR;
	FOR(i, mid + 1, r){
		tmp = ask(i);
		if (tmp[0] + tmp[1] == 0){
			ANS = i;
			DONE = true;
			return;
		}
		if (tmp[0] + tmp[1] == SCORE){
			rp = i;
			rL = tmp[0];
			rR = tmp[1];
			break;
		}
	}
	int lp = r;
	int lL;
	int lR;
	for (int i = mid - 1; i >= l; --i){
		tmp = ask(i);
		if (tmp[0] + tmp[1] == 0){
			ANS = i;
			DONE = true;
			return;
		}
		if (tmp[0] + tmp[1] == SCORE){
			lp = i;
			lL = tmp[0];
			lR = tmp[1];
			break;
		}
	}
	if (rp != l){
		findAll(rp + 1, r, rL, R);
	}
	if (lp != r){
		findAll(l, lp, L, lR);
	}

}

int find_best(int n) {
	DONE = false;
	int score = 0;
	FOR(i, 0, min(476, n)){
		vector<int> tmp = ask(i);
		score = max(score, tmp[0] + tmp[1]);
		if (tmp[0] + tmp[1] == 0){
			return i;
		}
	}
	SCORE = score;
	findAll(476, n, 0, 0);
	return ANS;
}

Compilation message (stderr)

prize.cpp: In function 'void findAll(int, int, int, int)':
prize.cpp:32:6: warning: variable 'rR' set but not used [-Wunused-but-set-variable]
   32 |  int rR;
      |      ^~
prize.cpp:48:6: warning: variable 'lL' set but not used [-Wunused-but-set-variable]
   48 |  int lL;
      |      ^~
prize.cpp:68:10: warning: 'lR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |   findAll(l, lp, L, lR);
      |   ~~~~~~~^~~~~~~~~~~~~~
prize.cpp:65:10: warning: 'rL' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |   findAll(rp + 1, r, rL, R);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~

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