Submission #828057

#	Time	Username	Problem	Language	Result	Execution time	Memory
828057		tranxuanbach	The Big Prize (IOI17_prize)	C++17	20 / 100	3 ms	5072 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n;
vector <int> query_answer[N];
int cnt_left[N], cnt_right[N];
int type[N];

void query(int x){
	if (not query_answer[x].empty()){
		return;
	}
	query_answer[x] = ask(x);
	cnt_left[x] = query_answer[x].front();
	cnt_right[x] = query_answer[x].back();
	type[x] = accumulate(query_answer[x].begin(), query_answer[x].end(), 0);
}

int find_best(int _n){
	n = _n;
	int lo = 0, hi = n - 1;
	while (lo < hi){
		int mid = (lo + hi) >> 1;
		query(mid);
		if (type[mid] == 0){
			return mid;
		}
		if (cnt_left[mid]){
			hi = mid - 1;
		}
		else{
			lo = mid + 1;
		}
	}
	return lo;
}

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