Submission #118607

# Submission time Handle Problem Language Result Execution time Memory
118607 2019-06-19T09:44:30 Z StevenH The Big Prize (IOI17_prize) C++14
0 / 100
6 ms 512 KB
#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;
	
	while(mid-k>=l && mid+k<=r)
	{
		k++;
		if(!vis[mid+k] && mid<=r)
		{
			tp=mid+k;
			break;
		}
		else if(!vis[mid-k] && mid>=l)
		{
			tp=mid-k;
			break;
		}
	}
	if(tp==-1)return 0;
	/*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;*/
	
	mid=tp;
	
	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

prize.cpp: In function 'int find(int, int, int, int)':
prize.cpp:60: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:66:15: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int mx=-1,nm,id;
               ^~
prize.cpp:66:12: warning: 'nm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int mx=-1,nm,id;
            ^~
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB answer is not correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB answer is not correct
2 Halted 0 ms 0 KB -