Submission #297972

#	Time	Username	Problem	Language	Result	Execution time	Memory
297972		Batyr	The Big Prize (IOI17_prize)	C++17	90 / 100	91 ms	2816 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int>

const int maxn=2e5+5;
int dp[maxn][3];

//~ vector<int> ask(int pos){
	//~ cout<<pos<<'\n';
	//~ int a,b;
	//~ cin >> a >> b;
	//~ return {a,b};
//}

pii f(int l,int r){
	//~ cout<<l<<' '<<r<<'\n';
	if(dp[l][0] == -1 and dp[l][1]==-1){
		vector<int> p = ask(l);
		dp[l][0]=p[0];
		dp[l][1]=p[1];
	}
	if(dp[r][0]==-1 and dp[r][1]==-1){
		vector<int> p = ask(r);
		dp[r][0] = p[0];
		dp[r][1] = p[1];
	}
	
	if(dp[l][0]+dp[l][1]==0) return {0,l};
	if(dp[r][0]+dp[r][1]==0) return {0,r};
	
	if(dp[l][0]+dp[l][1] == dp[r][0]+dp[r][1] and dp[r][0]-dp[l][0]==0) return {dp[r][0]+dp[r][1],r};
	
	pii cep = f(l,(l+r)/2);
	pii sag = f((l+r)/2+1,r);
	if(cep.ff < sag.ff) return cep;
	
	return sag;
}

int find_best(int n){
	memset(dp,-1,sizeof(dp));
	pii p = f(0,n-1);
	return p.ss;
}

//~ int main(){
	//~ int n;
	//~ cin >> n;
	//~ cout << find_best(n);
//}

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