Submission #559722

#	Time	Username	Problem	Language	Result	Execution time	Memory
559722		jamezzz	The Big Prize (IOI17_prize)	C++17	0 / 100	3055 ms	14872 KiB

prize

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

int ans,worst;
mt19937 rng(time(0));

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

void dnc(vector<int> v,int good,int lgood,int rgood){
	//printf("dnc: {");
	//for(int i:v)printf("%d ",i);
	//printf("} %d %d %d\n",good,lgood,rgood);
	if(good==0)return;
	if(v.size()==0)return;
	
	int m=v.size()/2;
	int s=m;
	while(m<v.size()){
		vector<int> res=myask(m);
		if(res[0]+res[1]==0){
			ans=m;return;
		}
		if(res[0]+res[1]==worst){
			int mid=m-s;
			vector<int> l,r;
			for(int i=0;i<s;++i)l.push_back(v[i]);
			for(int i=m+1;i<v.size();++i)r.push_back(v[i]);
			dnc(l,res[0]-mid-lgood,res[0],res[1]+mid);
			dnc(r,res[1]-mid-rgood,res[0]+mid,res[1]);
		}
		else ++m;
	}
	
	vector<int> l;
	int mid=m-s;
	for(int i=0;i<s;++i)l.push_back(v[i]);
	dnc(l,good-mid,lgood,rgood+mid);
}

int find_best(int n){
	memo.resize(n);
	for(int i=0;i<n;++i)memo[i].resize(2,-1);
	
	for(int i=0;i<min(n,500);++i){
		int x=rng()%n;
		vector<int> res=myask(x);
		worst=max(worst,res[0]+res[1]);
		if(res[0]+res[1]==0)return x;
	}
	
	vector<int> v;
	for(int i=0;i<n;++i)v.push_back(i);
	
	dnc(v,worst,0,0);
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void dnc(std::vector<int>, int, int, int)':
prize.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  while(m<v.size()){
      |        ~^~~~~~~~~
prize.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int i=m+1;i<v.size();++i)r.push_back(v[i]);
      |                  ~^~~~~~~~~

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