Submission #118610

#	Time	Username	Problem	Language	Result	Execution time	Memory
118610		StevenH	The Big Prize (IOI17_prize)	C++14	96.16 / 100	58 ms	648 KiB

prize

#include "prize.h"
#include <cstring>
//#include <bits\stdc++.h> 
using namespace std;
const int maxn = 200005;
bool vis[maxn];
int lp;
									//rx right of r
int find(int l,int r,int lx,int rx)	//lx left of l
{
	int mid,tmp,nm;
	mid=(l+r)/2;
	int k=0,tp=-1;
	
	if(vis[mid])
	{
		while(mid-k>=l || mid+k<=r)
		{
			k++;
			if(!vis[mid+k] && mid+k<=r)
			{
				tp=mid+k;
				break;
			}
			else if(!vis[mid-k] && mid-k>=l)
			{
				tp=mid-k;
				break;
			}
		}
		if(tp==-1)return 0;
		mid=tp;
	}
	/*while(vis[mid] && mid<=r)mid++;
	if(mid>r)
	{
		mid=(l+r)/2;
		while(vis[mid] && mid>=l)mid--;
		if(mid<l)return 0;	// 0 not find any thing
	}
	
	if(mid<l || mid>199999)return 0;*/
	
	
	vector<int> res = ask(mid);
	vis[mid]=true;
	if(res[0]+res[1]==0)return mid;
	
	
	else if(res[0]+res[1]==lp)
	{
		if(res[0]-lx>0)	 // left not empty 
		{
			tmp=find(l,mid-1,lx,res[1]);
			if(tmp)return tmp;
		}
		if(res[1]-rx>0)	// right not empty
		{
			tmp=find(mid+1,r,res[0],rx);
			if(tmp)return tmp;
		}
	}
	else if(tmp=find(l,r,lx,rx))return tmp;
	
	return 0;
}

int find_best(int n) {
	int mx=-1,nm,id;
	//vector<int> res = ask(i);
	for(int i=0;i<476;i++)
	{
		vector<int> res = ask(i);
		int tmp = res[0] + res[1];
		if(tmp==0)
		{
			//cout<<i;
			return i;
		}
		if(tmp>mx)
		{
			mx=tmp;
			id=i;
			nm=1;
		}
		if(tmp==mx)nm++;
	}
	
	lp=mx;	//lp refers to lollipop
	memset(vis,false,sizeof(vis));
	int tp=find(476,n-1,476-nm,0);
	//cout<<tp;
	return tp;
	
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find(int, int, int, int)':
prize.cpp:63:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  else if(tmp=find(l,r,lx,rx))return tmp;
          ~~~^~~~~~~~~~~~~~~~
prize.cpp:11:14: warning: unused variable 'nm' [-Wunused-variable]
  int mid,tmp,nm;
              ^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:69:15: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int mx=-1,nm,id;
               ^~
prize.cpp:69:12: warning: 'nm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int mx=-1,nm,id;
            ^~

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