oj.uz

Submission #625386

# Submission time Handle Problem Language Result Execution time Memory
625386 2022-08-10T10:04:53 Z lollipop The Big Prize (IOI17_prize) C++17
20 / 100
 96 ms 528 KB 
#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 , int n ){
    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( 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 ff = 0 ;
        while( true ){
            cnt ++ ;
           // if( cnt > 10000 ) assert(0) ;
            vector < int > ve = ask( indx ) ;
            if( indx == ( l + r ) / 2 ) ff = ve[ 1 ] ;
            if( ve[ 0 ] + ve[ 1 ] != mx ){
                if( ve[ 0 ] + ve[ 1 ] == 0 ){
                    return indx ;
                }
                add( indx , n ) ;
                if( indx != l ) indx -- ;
                else{
                    ff = ff - get_sum( r + 1 , n - 1 ) ;
                    if( ff != 0 ) v.pb( { ( l + r ) / 2 + 1 , r } ) ;
                }
            }
            else{
                   // 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 
                    L = ( l + r ) / 2 + 1 ;
                    R = r ;
                    lft = ff ;
                    lft = lft - get_sum( r + 1 , n - 1 ) ;
                   if( lft != 0 && L <= R ){
                       v.pb( { L , R } ) ;
                   }
                break ;
            }
        }
        
    }
}

Compilation message

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 3 ms 300 KB Output is correct
4 Correct 5 ms 308 KB Output is correct
5 Correct 2 ms 308 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 4 ms 208 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 4 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 2 ms 300 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 5 ms 308 KB Output is correct
8 Correct 3 ms 308 KB Output is correct
9 Correct 4 ms 304 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
11 Incorrect 96 ms 528 KB Incorrect
12 Halted 0 ms 0 KB -