Submission #1062390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062390		Muhammad_Aneeq	커다란 상품 (IOI17_prize)	C++17	90 / 100	65 ms	5988 KiB

prize

#include "prize.h"
#include <vector>
#include <iostream>
#include <random>
using namespace std;
int const N=2e5+10;
bool vis[N]={};
vector<int>val[N];
vector<int> qu(int i)
{
	if (vis[i])
		return val[i];
	vis[i]=1;
	val[i]=ask(i);
	return val[i];
}
int find_best(int n)
{
	srand(time(0));
	int mx=0;
	for (int i=0;i<min(n,100);i++)
	{
		int x=rand()%n;
		if (vis[x])
		{
			i--;
			continue;
		}
		vector<int>g=qu(x);
		if (g[0]+g[1]>mx)
			mx=g[0]+g[1];
	}
	int st=0;
	while (1)
	{
		vector<int>g=qu(st);
		if (g[0]==0&&g[1]==0)
			break;
		if (g[0]+g[1]>=mx)
		{
			int en=n;
          	mx=g[0]+g[1];
			while (st+1<en)
			{
				int mid=(st+en)/2;
				if (mid<n&&qu(mid)==g)
					st=mid;
				else
					en=mid;
			}
		}
		st++;
	}
	return st;
}

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