Submission #64474

#	Time	Username	Problem	Language	Result	Execution time	Memory
64474		FLDutchman	Robots (IOI13_robots)	C++14	0 / 100	4 ms	620 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define H(x) //cout << #x << " " << x << endl;


typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

int A, B, T;
// weight, size
vii toys;
vi weaks, smalls;

int ok(int k){
    priority_queue<int> q;
    int i = 0;
    FOR(a, 0, A){
        for(; toys[i].fst < weaks[a]; i++) q.push(toys[i].snd);
        FOR(_, 0, k) {
            if(q.empty()) break;
            //cout << q.top() << endl;
            q.pop();
        }
    }
    for(; i < T; i++) q.push(toys[i].snd);
    H(q.size());
    for(int s : smalls){
        FOR(_, 0, k){
            if(q.empty()) break;
            if(q.top() >= s) return 0;
            q.pop();
        }
    }
    if(!q.empty()) return 0;
    return 1;
}

INT putaway(INT a, INT b, INT t, INT X[], INT Y[], INT W[], INT S[]) {
    A = a; B = b; T = t;
    FOR(i, 0, A) weaks.pb(X[i]);
    FOR(i, 0, B) smalls.pb(Y[i]);
    sort(weaks.begin(), weaks.end());
    sort(smalls.begin(), smalls.end(), greater<int>());
    FOR(i, 0, T) toys.pb({W[i], S[i]});
    sort(toys.begin(), toys.end());
    int lb = 0, rb = T+1;
    while(lb + 1 != rb){
        //cout << lb << " " << rb << endl;
        int mb = (lb+rb)/2;
        if(ok(mb)) rb = mb;
        else lb = mb;        
    }
    return rb == T+1 ? -1 : rb;
}

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