Submission #431252

#	Time	Username	Problem	Language	Result	Execution time	Memory
431252		Belgutei	The Big Prize (IOI17_prize)	C++17	0 / 100	7 ms	320 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

vector<int> v; 
int ans,mx;

void solve(){
	for(int i=0; i<=5000; i++){
		vector<int> vv;
		vv=ask(i);
		if(vv[0]==0 && vv[1]==0){
			ans=i;
			break;
		}
	}
}

void dfs(int x, int y){
	if(x>y) return;
	vector<int> v1;
	vector<int> v2;
	v1=ask(x);
	if(x==y){
		if(v1[0]+v1[1]!=mx) v.pb(x);
		return;
	}
	v2=ask(y);
	int a=v1[0];
	int b=v1[1];
	int c=v2[0];
	int d=v2[1];
	if(a+b==mx && c+d==mx){
		if(c-a==0 || x==y) return;
		int mid=(x+y)/2;
		dfs(x+1,mid);
		dfs(mid+1,y);
	}
	else{
		if(a+b<mx && c+d<mx){
			v.pb(x);
			v.pb(y);
			dfs(x+1,y-1);
			return;
		}
		if(a+b<mx){
			v.pb(x);
			dfs(x+1,y);
			return;
		}
		v.pb(y);
		dfs(x,y-1);
	}
}

int find_best(int n) {
	if(n<=5000){
		solve();
		return ans;
	}
	for(int i=0; i<=500; i++){
		vector<int> vv;
		vv=ask(i);
		if(vv[0]==0 && vv[1]==0){
			return i;
		}
		mx=max(mx,vv[0]+vv[1]);
	}
	int l=0;
	int r=n-1;
	dfs(l,r);

	for(int i=0; i<v.size(); i++){
		vector<int> vv;
		vv=ask(i);
		if(vv[0]==0 && vv[1]==0){
			return i;
		}
	}
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~

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