Submission #138442

#	Time	Username	Problem	Language	Result	Execution time	Memory
138442		CaroLinda	The Big Prize (IOI17_prize)	C++14	97.66 / 100	64 ms	2296 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 474

const int MAXN = 2e5+10 ;

using namespace std ;

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


int n , lollipop , found = -1 ;

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 ) ; }

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

void Ask(int idx)
{

	if( marc[idx] ) return ;

	marc[idx] = true ;

	vector<int> temp = ask(idx) ;

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

}

void findLollipop()
{

	lollipop = -1 ;

	lp(i,0, min( n , 475 ) )
	{
		
		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(isDiamond(i)) found = 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(isDiamond(i)) found = 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) ;

	bb.push( mk(findR(0,n-1) , findL(0,n-1) ) ) ;

	if(found!=-1) return found ;


	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(isDiamond(mid)) return 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) ;

			if(found!=-1) return found ;

		}

		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( isDiamond(i) ) return i ;

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:105: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:142: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:142: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:142: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:142: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:142: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:142: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:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
prize.cpp: In function 'int findR(int, int)':
prize.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:152:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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