Submission #625651

#	Time	Username	Problem	Language	Result	Execution time	Memory
625651		lollipop	The Big Prize (IOI17_prize)	C++17	20 / 100	97 ms	884 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
const int N = 2e5 + 10 ; 
int fen[ N ] ;
void add( int i ){
    i ++ ; 
    for( int j = i ; j <= N ; j = j + ( j & ( - j ) ) ) fen[ j ] += 1 ;
}
int get_sum( int l , int r ){
    r ++ ;
    int sum = 0 ; 
    for( int j = r ; j > 0 ; j = j - ( j & ( - j ) ) ) sum += fen[ j ] ;
    for( int j = l ; j > 0 ; j = j - ( j & ( - j ) ) ) sum -= fen[ j ] ;
    return sum ;
}
int find_best( int n ) {
    int mx = 0 ;
    int cnt = 0 ;
    for( int i = 0 ; i < min( n , 500 ) ; i ++ ){
        cnt ++ ;
        vector < int > v ;
        v = ask( i ) ;
        mx = max( mx , v[ 0 ] + v[ 1 ] ) ;
    }
    vector < pair < int , int > > v ;
    v.pb( { 0 , n - 1 } ) ;
    while( true ){
        if( cnt > 10000 ) assert( 0 ) ;
        if( v.size() == 0 ) break ;
        int sz = v.size() - 1 ;
        int l = v[ sz ].f ;
        int r = v[ sz ].s ;
        v.pop_back() ;
        int indx = ( l + r ) / 2 ;
        int tt = 0 ;
        while( true ){
            cnt ++ ;
            vector < int > ve = ask( indx ) ;
            if( ve[ 0 ] + ve[ 1 ] != mx ){
                if( ve[ 0 ] + ve[ 1 ] == 0 ){
                    return indx ;
                }
                add( indx ) ;
                if( tt == 0 && indx != l ) indx -- ;
                else{
                    if( tt == 1 ) indx ++ ;
                    else{
                        indx = ( l + r ) / 2 + 1 ; 
                        tt = 1 ;
                    }
                    if( indx > r ) break ;
                }
            }
            else{
               if( tt == 0 ){
                   // left part 
                   int L = l ;
                   int R = indx - 1 ;
                   int lft = ve[ 0 ] ;
                   lft = lft - get_sum( -1 , l - 1 ) ;
                   if( lft != 0 && L <= R ){
                       v.pb( { L , R } ) ;
                   }
                   // right part 
                   /*
                     while( true ){
                       if( indx > r ) break ;
                       ve = ask( indx ) ; 
                       if( ve[ 0 ] + ve[ 1 ] == 0 ){
                        return indx ;
                       }
                       if( ve[ 0 ] + ve[ 1 ] == mx ) break ;
                       add( indx ) ;
                       indx ++ ;
                   } 
                     L = indx + 1 ;
                     R = r ;
                     lft = ve[ 1 ] ;
                    lft = lft - get_sum( r + 1 , N - 1 ) ;
                   if( lft != 0 && L <= R ){
                       v.pb( { L , R } ) ;
                   } */
                    L = ( l + r ) / 2 + 1 ;
                    R = r ;
                    lft = ve[ 1 ] ;
                    lft = lft - get_sum( r + 1 , n - 1 ) ;
                   if( lft != 0 && L <= R ){
                       v.pb( { L , R } ) ;
                   } 
               }
               else{
                   // right part 
                    int L = indx + 1 ;
                    int R = r ;
                    int lft = ve[ 1 ] ;
                    lft = lft - get_sum( r + 1 , n - 1 ) ;
                   if( lft != 0 && L <= R ){
                       v.pb( { L , R } ) ;
                   }
               }
                break ;
            }
        }
        
    }
}

Compilation message (stderr)

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

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