Submission #1193327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193327		salmon	The Big Prize (IOI17_prize)	C++20	100 / 100	11 ms	408 KiB

prize

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

int N;
set<int,greater<int>> sat;

int solve(int s, int e, int lv, int rv, int tot){
	if(s > e) return -1;
	if(lv + rv == tot) return -1; 
	
	int m = (s + e)/2;
	
	vector<int> temp = ask(m);
	
	int sum = temp[0] + temp[1];
	
	if(sum == 0) return m;
	
	if(tot < sum){
		tot = sum;
		int store = solve(0,m - 1, 0, temp[1],tot); 
		if(store != -1) return store;
		return solve(m + 1, N - 1, temp[0], 0,tot); 
	}
	else if(tot == sum){
		int store = solve(s,m - 1, lv, temp[1],tot); 
		if(store != -1) return store;
		return solve(m + 1, e, temp[0], rv,tot); 
	}
	else{
		for(int i = m + 1; i <= e; i++){
			vector<int> temp = ask(i);
	
			int sum = temp[0] + temp[1];
			
			if(sum == 0) return i;
			if(sum == tot){
				int store = solve(s,m - 1, lv, temp[1] + i - m,tot); 
				if(store != -1) return store;
				return solve(i + 1, e, temp[0], rv,tot); 
			}
			else if(tot < sum){
				tot = sum;
				int store = solve(0,m - 1, 0, temp[1],tot); 
				if(store != -1) return store;
				return solve(m + 1, N - 1, temp[0], 0,tot); 
			}
		}
		
		for(int i = m - 1; i >= s; i--){
			vector<int> temp = ask(i);
	
			int sum = temp[0] + temp[1];
			
			if(sum == 0) return i;
			if(sum == tot){
				return solve(s, i - 1, lv, temp[1],tot); 
			}
			else if(tot < sum){
				tot = sum;
				int store = solve(0,m - 1, 0, temp[1],tot); 
				if(store != -1) return store;
				return solve(m + 1, N - 1, temp[0], 0,tot); 
			}
		}
		
		return -1;
	}
}

int find_best(int N) {
	::N = N;
	
	int s = 0;
	int e = N - 1;
	
	return solve(s,e,0,0,-1);
}

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