Submission #307308

#	Time	Username	Problem	Language	Result	Execution time	Memory
307308		CaroLinda	The Big Prize (IOI17_prize)	C++14	0 / 100	83 ms	636 KiB

prize

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

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()

const int MAX = 2e5+10 ;

using namespace std ;

int soma[MAX] ;
int record[MAX][2] ;
bool went[MAX] ;

bool isLollipop(int qtd) { return qtd >= 279 ; }
bool isDiamond(int qtd) { return qtd == 0; }

void pergunta(int i)
{
	if(went[i]) return ;

	went[i] = true ;

	vector<int> a = ask(i) ;

	record[i][0] = a[0] ;
	record[i][1]= a[1] ;
	soma[i] = a[0] + a[1] ;
}

int find_best(int n) 
{
	
	vector<pii> fila(1);

	for(int i = 0 ; i < n ; i++ )
	{
		pergunta(i) ;
		
		if( isDiamond(soma[i]) ) return i ;
		if( !isLollipop(soma[i]) ) continue ;
		
		fila[0].ff = i+1 ;
		break ;

	}
	for(int i= n-1 ; i >= 0 ; i-- )
	{
		pergunta(i) ;

		if(isDiamond(soma[i])) return i ;
		if( !isLollipop(soma[i]) ) continue ;

		fila[0].ss = i-1 ;
		break ;
	}

	int ptr = 0 ;
	while( ptr < sz(fila) )
	{
		int l = fila[ptr].ff ;
		int r = fila[ptr].ss ;
		ptr++ ;

		int mid = (l+r)>>1 ;

		pergunta(mid);

		//Calculate left interval
		int newR = mid ;
		while( true )
		{
			pergunta(newR) ;

			if(isDiamond(newR)) return newR ;
			if( !isLollipop(newR) ) newR-- ;
			else break ;
		}
		
		newR-- ;

		if( l <= newR && (record[l-1][1] - record[newR+1][1] > 0 ) ) 
		{
			fila.push_back( make_pair(l,newR) ) ;
		}

		//Calculate right interval
		int newL = mid ;
		while( true )
		{
			pergunta(newL) ;

			if( isDiamond(newL) ) return newL ;
			if(!isLollipop(newL)) newL++ ;
			else break ;
		}

		newL++ ;

		if( newL <= r && (record[newL-1][1] - record[r+1][1]) > 0 )
			fila.push_back( make_pair(newL, r) ) ;
	}

	return 0;
}

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