Submission #431286

#	Time	Username	Problem	Language	Result	Execution time	Memory
431286		Belgutei	The Big Prize (IOI17_prize)	C++17	0 / 100	5 ms	284 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(int k){
	for(int i=0; i<k; 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(n);
		return ans;
	}
	
	for(int i=0; i<min(500,n); i++){
		vector<int> vv;
		vv=ask(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:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~

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