Submission #132070

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

prize

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

vector< vector< int > > memo;

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

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

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:13:6: warning: variable 'poppy_index' set but not used [-Wunused-but-set-variable]
  int poppy_index = -1;
      ^~~~~~~~~~~

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