Submission #921891

#	Time	Username	Problem	Language	Result	Execution time	Memory
921891		Alihan_8	Robots (IOI13_robots)	C++17	100 / 100	1327 ms	24852 KiB

robots

#include <bits/stdc++.h>

#include "robots.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector <int> x, y;
    vector <ar<int,2>> p;
    for ( int i = 0; i < A; i++ ){
        x.pb(X[i]);
    }
    for ( int i = 0; i < B; i++ ){
        y.pb(Y[i]);
    }
    for ( int i = 0; i < T; i++ ){
        p.pb({W[i], S[i]});
    }
    sort(all(p)), sort(all(x)), sort(all(y));
    reverse(all(y));
    auto ok = [&](int k){
        priority_queue <int> q;
        int j = 0;
        for ( auto &i: x ){
            while ( j < T && p[j][0] < i ){
                q.push(p[j][1]);
                j++;
            }
            int f = k;
            while ( f > 0 && !q.empty() ){
                q.pop(); --f;
            }
        }
        while ( j < T ){
            q.push(p[j][1]);
            j++;
        }
        for ( auto &i: y ){
            if ( q.empty() ) break;
            if ( q.top() >= i ){
                return false;
            }
            int f = k;
            while ( f > 0 && !q.empty() ){
                q.pop(), --f;
            }
        }
        return q.empty();
    };
    int l = 0, r = T + 1;
    while ( l < r ){
        int md = (l + r) / 2;
        if ( ok(md) ) r = md;
        else l = md + 1;
    }
    if ( l == T + 1 ){
        return -1;
    } return l;
}

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