Submission #1000405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000405		vjudge1	The Big Prize (IOI17_prize)	C++17	100 / 100	30 ms	5684 KiB

prize

#include"prize.h"
using namespace std;
int tot,now;vector<int>a[200009],b;
inline int sum(int i)
{
	if(a[i].empty())a[i]=ask(i);
	return a[i][0]+a[i][1];
}
inline int lft(int i)
{
	if(a[i].empty())a[i]=ask(i);
	return a[i][0];
}
inline int dfs(int l,int r)
{
	if(l>r)return-1;
	if(!sum(r))return r;
	if(sum(r)^tot)
	{
		int x=dfs(l,r-1);
		if(x>>31)++now;
		return x;
	}
	if(lft(r)==now)return-1;
	int mid=l+r>>1,x=dfs(l,mid);
	if(x>>31)x=dfs(mid+1,r);
	return x;
}
int find_best(int n)
{
	b.emplace_back(-1);
	for(int i=0;i<n&&i<500;++i)b.emplace_back(b.back()+
		(n-1-b.back()-1)/(500-i)+1);
	for(int i=1;i<b.size();++i)if(!sum(b[i]))return b[i];
	for(int i=1;i<b.size();++i)if(sum(b[i])>tot)tot=sum(b[i]);
	for(int i=1;i<b.size();++i)
	{
		int x=dfs(b[i-1]+1,b[i]);
		if(~x)return x;
	}
}

Compilation message (stderr)

prize.cpp: In function 'int dfs(int, int)':
prize.cpp:25:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |  int mid=l+r>>1,x=dfs(l,mid);
      |          ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=1;i<b.size();++i)if(!sum(b[i]))return b[i];
      |              ~^~~~~~~~~
prize.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=1;i<b.size();++i)if(sum(b[i])>tot)tot=sum(b[i]);
      |              ~^~~~~~~~~
prize.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=1;i<b.size();++i)
      |              ~^~~~~~~~~
prize.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

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