Submission #132099

#	Time	Username	Problem	Language	Result	Execution time	Memory
132099		MoNsTeR_CuBe	The Big Prize (IOI17_prize)	C++17	20 / 100	158 ms	44780 KiB

prize

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

vector< vector< int > > memo;

int TOT = 0;

vector< int > ASK(int a){
	if(memo[a][0] != -1) return memo[a];
	else{
		TOT++;
		assert(TOT < 10000);
		return memo[a] = ask(a);
	} 
}

int find_best(int n) {
	int poppy_index = -1;
	int poppy_tot = 0;
	
	vector< vector< int > > rem(n+1, vector< int > (2));
	
	memo.resize(n, vector< int >(2,-1));
	
	for(int i = 0; i < min(n,300); i++){
		vector< int > query = ASK(i);
		rem[query[0] + query[1]] = query;
		if(query[0] + query[1] >= poppy_tot){
			poppy_tot = query[0] + query[1];
			poppy_index = i;
		}else if(query[0] + query[1] == 0){
			return i;
		}
	}
	
	int curr = poppy_index+1;
	
	while(curr < n){
		vector< int > query = ASK(curr);
		rem[query[0] + query[1]] = query;
		if(query[0] + query[1] == 0) return curr;
		while(query[0] + query[1] != poppy_tot){
			curr++;
			query = ASK(curr);
			rem[query[0] + query[1]] = query;
			if(query[0] + query[1] == 0) return curr;
		}
		int left = curr+1;
		int right = n-1;
		
		while(left < right){
			int mid = (left+right)/2;
			vector< int > Q = ASK(mid);
			if(Q[0] + Q[1] == 0) return mid;
			if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] == 0){
				left = mid+1;
				rem[Q[0] + Q[1]] = Q;
			} 
			else if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] > 0) right = mid-1;
			else if(Q[0] + Q[1] != poppy_tot && Q[0] - rem[Q[0] + Q[1]][0] == 0){
				left = mid+1;
				rem[Q[0] + Q[1]] = Q;
			} 
			else right = mid;
		}
		
		curr = left;
	}
	return 0;
}

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