Submission #131205

#	Time	Username	Problem	Language	Result	Execution time	Memory
131205		amiratou	The Big Prize (IOI17_prize)	C++14	0 / 100	58 ms	5196 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dp[200002];
bool check(int med,int idx){
	vector<int> res;
	if(!dp[med].empty())res=dp[med];
	else res=ask(med),dp[med]=res;
	if(dp[idx].empty())dp[idx]=ask(idx);
	return (dp[idx][0]==res[0]&&dp[idx][1]==res[1]);
}
int find_best(int n) {
	/*for (int i = 29979; i < 29979+sqrt(n); ++i)
	{
		cerr<<ask(i)[0]<<" "<<ask(i)[1]<<"\n";
	}*/
	int s=sqrt(n),l=0;
	int maxi=0,idx=0,last=idx;
	for (int i = 0; i < min(477,n); ++i)
	{
		dp[i]=ask(i);
		if(dp[i][0]+dp[i][1]==0)return i;
		if(dp[i][0]+dp[i][1]>=maxi)maxi=dp[i][0]+dp[i][1],idx=i;
	}
	for (int j = 477; j < n; j+=s)
	{
		//cerr<<j<<"a\n";
		while(idx<(j+s-1)){
			int l=idx+1,r=j+s-1,ans=idx;
			while(l<=r){
				int med=(l+r)/2;
				if(check(med,idx))ans=med,l=med+1;
				else r=med-1;
				if(med<n&&dp[med][0]+dp[med][1]==0)return med;
			}
			ans++;
			while(ans<(j+s)){
				vector<int> res;
				if(!dp[ans].empty())res=dp[ans];
				else res=ask(ans),dp[ans]=res;
				if(dp[ans][0]+dp[ans][1]==0)return ans;
				if(dp[ans][0]+dp[ans][1]>=maxi){
					maxi=dp[ans][0]+dp[ans][1],idx=ans;
					break;
				}
				ans++;
			}
			if(ans>=(j+s)){idx=j+s;}
		}
		for (int i = idx; i < min(j+s,n); i++)
		{
			//cerr<<i<<"\n";
			dp[i]=ask(i);
			if(dp[i][0]+dp[i][1]==0)return i;
			if(dp[i][0]+dp[i][1]>=maxi){maxi=dp[i][0]+dp[i][1];idx=i;break;}
		}
	}
	//cerr<<last;
	for (int i = idx; i < n; ++i)
	{
		dp[i]=ask(i);
		if(dp[i][0]+dp[i][1]==0)return i;
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:17:16: warning: unused variable 'l' [-Wunused-variable]
  int s=sqrt(n),l=0;
                ^
prize.cpp:18:19: warning: unused variable 'last' [-Wunused-variable]
  int maxi=0,idx=0,last=idx;
                   ^~~~

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