Submission #290004

#TimeUsernameProblemLanguageResultExecution timeMemory
290004BadrangiikhRobots (IOI13_robots)C++14
0 / 100
1 ms384 KiB
#include "robots.h" #include<bits/stdc++.h> using namespace std; int n , m , k , l , r , mid , x , y , z , ans , cnt , s1 , s2 , s3 , s4 ; int weak [ 50005 ] ; int smol [ 50005 ] ; pair < int , int > toy [ 1000005 ] ; int w [ 1000005 ] ; int s [ 1000005 ] ; priority_queue < int > pq , pp ; vector < int > vc , vv ; bool check ( int s1 ) { pq = pp ; int s2 = 0 ; for ( int i = 0 ; i < m ; i ++ ) { while ( s2 < n && toy [ s2 ] . first < weak [ i ] ) { pq . push ( s [ toy [ s2 ] . second ] ) ; s2 ++ ; } s3 = s1 ; while ( s3 -- && pq . size ( ) > 0 ) pq . pop ( ) ; } for ( ; s2 < n ; s2 ++ ) { pq . push ( s [ toy [ s2 ] . second ] ) ; } vc = vv ; while ( pq . size ( ) > 0 ) { vc . push_back ( pq . top ( ) ) ; pq . pop ( ) ; } reverse ( vc . begin ( ) , vc . end ( ) ) ; s2 = 0 ; s3 = s1 ; for ( auto it : vc ){ while ( s2 < k && ( s3 == 0 || it >= smol [ s2 ] ) ){ s2 ++ ; s3 = k ; } if ( s2 == k ) return 0 ; s3 -- ; } return 1 ; } int putaway ( int A, int B, int T, int X[], int Y[], int W[], int S[]) { m = A ; k = B ; n = T ; for ( int i = 0 ; i < m ; i ++ ) { weak [ i ] = X [ i ] ; } if ( m > 0 ) { sort ( weak , weak + m ) ; } else { weak [ 0 ] = 0 ; } for ( int i = 0 ; i < k ; i ++ ) { smol [ i ] = Y [ i ] ; } if ( k > 0 ) { sort ( smol , smol + k ) ; } else { smol [ 0 ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { w [ i ] = W [ i ] ; s [ i ] = S [ i ] ; } for ( int i = 0 ; i < n ; i ++ ) { if ( w [ i ] > weak [ m ] && s [ i ] > smol [ k ] ) { printf ( "-1" ) ; exit (0) ; } toy [ i ] . first = w [ i ] ; toy [ i ] . second = i ; } sort ( toy , toy + n ) ; l = ( n + m + k - 1 ) / ( m + k ) ; r = n ; while ( l < r ) { mid = ( l + r ) / 2 ; if ( check ( mid ) == 1 ) r = mid ; else l = mid + 1 ; } return l ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...