Submission #138437

#	Time	Username	Problem	Language	Result	Execution time	Memory
138437		CaroLinda	The Big Prize (IOI17_prize)	C++14	94.82 / 100	75 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 ;
     
    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:36: warning: left operand of comma operator has no effect [-Wunused-value]
      debug("My lollipop is %d\n" , lollipop) ;
                                    ^~~~~~~~
prize.cpp:8:16: warning: left operand of comma operator has no effect [-Wunused-value]
     #define ff first
                ^
prize.cpp:152:78: 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:16: warning: right operand of comma operator has no effect [-Wunused-value]
     #define ff first
                ^
prize.cpp:152:78: 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:16: warning: right operand of comma operator has no effect [-Wunused-value]
     #define ss second
                ^
prize.cpp:152:87: 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:16: warning: right operand of comma operator has no effect [-Wunused-value]
     #define ff first
                ^
prize.cpp:152:96: 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:103: 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:16: warning: right operand of comma operator has no effect [-Wunused-value]
     #define ss second
                ^
prize.cpp:152:111: 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:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^
prize.cpp: In function 'int findR(int, int)':
prize.cpp:110:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:162:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

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