#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 tt = 0 ;
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( 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
indx = ( l + r ) / 2 + 1 ;
while( true ){
if( indx > r ) break ;
cnt ++ ;
if( cnt > 10000 ) assert(0) ;
ve = ask( indx ) ;
if( ve[ 0 ] + ve[ 1 ] == 0 ){
return indx ;
}
if( ve[ 0 ] + ve[ 1 ] == mx ) break ;
add( indx , n ) ;
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 = ff ;
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
prize.cpp: In function 'int find_best(int)':
prize.cpp:47:13: warning: variable 'ff' set but not used [-Wunused-but-set-variable]
47 | int ff = 0 ;
| ^~
prize.cpp:37:35: warning: control reaches end of non-void function [-Wreturn-type]
37 | vector < pair < int , int > > v ;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
208 KB |
Output is correct |
| 2 |
Correct |
6 ms |
208 KB |
Output is correct |
| 3 |
Correct |
6 ms |
304 KB |
Output is correct |
| 4 |
Correct |
5 ms |
308 KB |
Output is correct |
| 5 |
Correct |
4 ms |
280 KB |
Output is correct |
| 6 |
Correct |
4 ms |
300 KB |
Output is correct |
| 7 |
Correct |
3 ms |
208 KB |
Output is correct |
| 8 |
Correct |
4 ms |
324 KB |
Output is correct |
| 9 |
Correct |
3 ms |
208 KB |
Output is correct |
| 10 |
Correct |
3 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
208 KB |
Output is correct |
| 2 |
Correct |
4 ms |
208 KB |
Output is correct |
| 3 |
Correct |
3 ms |
304 KB |
Output is correct |
| 4 |
Correct |
2 ms |
300 KB |
Output is correct |
| 5 |
Correct |
4 ms |
304 KB |
Output is correct |
| 6 |
Correct |
3 ms |
208 KB |
Output is correct |
| 7 |
Correct |
3 ms |
308 KB |
Output is correct |
| 8 |
Correct |
2 ms |
304 KB |
Output is correct |
| 9 |
Correct |
5 ms |
308 KB |
Output is correct |
| 10 |
Correct |
7 ms |
208 KB |
Output is correct |
| 11 |
Correct |
15 ms |
476 KB |
Output is correct |
| 12 |
Correct |
32 ms |
624 KB |
Output is correct |
| 13 |
Correct |
4 ms |
208 KB |
Output is correct |
| 14 |
Runtime error |
49 ms |
472 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
