Submission #283046

#	Time	Username	Problem	Language	Result	Execution time	Memory
283046		MohamedAhmed04	The Big Prize (IOI17_prize)	C++14	90 / 100	111 ms	5408 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
//#include "grader.cpp"

using namespace std ;

const int MAX = 2e5 + 10 ;

vector<int>val[MAX] ;

int cnt = 0 ;

vector<int> Ask(int idx)
{
	if(val[idx].size() == 0)
	{
		cnt++ ;
		assert(cnt <= 10000) ;
		val[idx] = ask(idx) ;
	}
	return val[idx] ;
}

int find_best(int n) 
{
	int maxcnt = 0 ;
	for(int i = 0 ; i < 500 ; ++i)
	{
		Ask(i) ;
		maxcnt = max(maxcnt , val[i][0] + val[i][1]) ;
		if(val[i][0] + val[i][1] == 0)
			return i ;
	}
	int st = -1 ;
	for(int i = 0 ; i < 500 ; ++i)
	{
		if(val[i][0] + val[i][1] == maxcnt)
		{
			st = i ;
			break ;
		}
	}
	assert(st != -1) ;
	vector<int>v ;
	for(int i = st ; i < n-1 ; ++i)
	{
		int l = i , r = n-1 ;
		int idx = n-1 ;
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			v = Ask(mid) ;
			if(v[0] == val[i][0] && v[1] == val[i][1])
				idx = mid , l = mid+1 ;
			else
				r = mid-1 ;
		}
		for(int j = idx+1 ; j < n ; ++j)
		{
			Ask(j) ;
			if(val[j][0] + val[j][1] == val[i][0] + val[i][1])
			{
				i = j-1 ;
				break ;	
			}
			if(val[j][0] == 0 && val[j][1] == 0)
				return j ;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:44:13: warning: control reaches end of non-void function [-Wreturn-type]
   44 |  vector<int>v ;
      |             ^

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