Submission #290035

#	Time	Username	Problem	Language	Result	Execution time	Memory
290035		Badrangiikh	Robots (IOI13_robots)	C++14	14 / 100	1855 ms	12540 KiB

robots

#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 ;
int *smol ;
pair < int , int > toy [ 1000005 ] ;
int *w ;
int *s ;
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 = s1 ;
        }
        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 ;
    weak = X ;
    sort ( weak , weak + m ) ;
    smol = Y ;
    sort ( smol , smol + k ) ;
    w = W ;
    s = S ;
    for ( int i = 0 ; i < n ; i ++ ) {
        if ( w [ i ] > weak [ m - 1 ] && s [ i ] > smol [ k - 1 ] ) {
            return -1 ; 
        }
        toy [ i ] . first = w [ i ] ;
        toy [ i ] . second = i ;
    }
    sort ( toy , toy + n ) ;
    l = 1 ;
    r = n ;
    while ( l < r ) {
        mid = ( l + r ) / 2 ;
        if ( check ( mid ) == 1 ) r = mid ;
        else l = mid + 1 ;
    }
    return l ;
}

• Subtask 1: 0 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10