| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 625625 | lollipop | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
while( true ){
if( indx > r ) break ;
ve = ask( 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 } ) ;
}
}
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 ;
}
}
}
}