Submission #138436

#	Time	Username	Problem	Language	Result	Execution time	Memory
138436		CaroLinda	The Big Prize (IOI17_prize)	C++14	94.83 / 100	72 ms	2200 KiB

prize

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

#define debug 
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define piiPrint(p) printf("%d %d\n" , p.ff , p.ss )
#define SQ 475

const int MAXN = 2e5+10 ;

using namespace std ;

// -------------------------------


int n , lollipop ;

pii p[MAXN] ;

queue<pii> bb ;

bool marc[MAXN] ;

// -------------------------------

int qtd( int ini , int fim ) { return p[fim].ff - p[ini].ff ; }

bool isLollipop( int idx ) { return ( p[idx].ff + p[idx].ss == lollipop ) ; }

void Ask(int idx)
{

	if( marc[idx] ) return ;

	marc[idx] = true ;

	vector<int> temp = ask(idx) ;

	p[idx] = mk( temp[0] , temp[1] ) ;

}

void receiveBlock(int l , int r)
{

	int resp[2] ;
	pii aux[2] = { mk(l,1) , mk( r , -1 ) } ;

	lp( j , 0, 2 )
		for(int i = aux[j].ff ; i >= l && i <= r ; i += aux[j].ss )
		{
			
			Ask(i) ;

			if(isLollipop(i)) { resp[j] = i ; break ; }

		}

	bb.push( mk(resp[0] , resp[1]) ) ;

}


void findLollipop()
{

	lollipop = -1 ;

	lp(i,0, min( n , SQ ) )
	{
		
		Ask(i) ;

		lollipop = max( lollipop , p[i].ff + p[i].ss ) ;

	}

}


int findL(int l , int x)
{

	for(int i = x ; i >= l ; i-- )
	{
		Ask(i) ;

		if( p[i].ff + p[i].ss == lollipop ) return i ;
	}

}


int findR(int x, int r)
{

	lp(i,x,r+1)
	{
		Ask(i) ;

		if(p[i].ff + p[i].ss == lollipop) return i ;
	}

}


int find_best(int N)
{

	n = N ;

	findLollipop() ;

	debug("My lollipop is %d\n" , lollipop) ;

	for(int i = 0 ; i < n ; i += SQ )
		receiveBlock(i , min( n-1 , i+SQ-1 ) ) ;


	while( !bb.empty() )
	{

		pii topo = bb.front() ;
		int mid = (topo.ff+topo.ss)/2 ;
		int l , r ;


		bb.pop() ;

		if( qtd( topo.ff, topo.ss ) == 0 ) continue ;

		Ask(mid) ;

		if( isLollipop(mid) ) l = r = mid ;
		else
		{

			//There is a mid such that l < mid < r
			//Because, if r - l = 1, then qtd = 0

			l = findL(topo.ff,mid) ;
			r = findR(mid, topo.ss) ;

		}

		debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;

		bb.push( mk(topo.ff, l) ) ;
		bb.push(mk(r,topo.ss)) ;

	}

	lp( i , 0 , n )
		if( marc[i] && p[i].ff + p[i].ss == 0 ) return i ;

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:120:32: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("My lollipop is %d\n" , lollipop) ;
                                ^~~~~~~~
prize.cpp:8:12: warning: left operand of comma operator has no effect [-Wunused-value]
 #define ff first
            ^
prize.cpp:152:74: note: in expansion of macro 'ff'
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                          ^~
prize.cpp:8:12: warning: right operand of comma operator has no effect [-Wunused-value]
 #define ff first
            ^
prize.cpp:152:74: note: in expansion of macro 'ff'
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                          ^~
prize.cpp:9:12: warning: right operand of comma operator has no effect [-Wunused-value]
 #define ss second
            ^
prize.cpp:152:83: note: in expansion of macro 'ss'
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                                   ^~
prize.cpp:8:12: warning: right operand of comma operator has no effect [-Wunused-value]
 #define ff first
            ^
prize.cpp:152:92: note: in expansion of macro 'ff'
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                                            ^~
prize.cpp:152:99: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                                                   ^
prize.cpp:9:12: warning: right operand of comma operator has no effect [-Wunused-value]
 #define ss second
            ^
prize.cpp:152:107: note: in expansion of macro 'ss'
   debug("I just splitted my interval from %d %d to %d %d %d %d\n" , topo.ff, topo.ss, topo.ff, l, r, topo.ss) ;
                                                                                                           ^~
prize.cpp: In function 'int findL(int, int)':
prize.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
prize.cpp: In function 'int findR(int, int)':
prize.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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