Submission #64498

#	Time	Username	Problem	Language	Result	Execution time	Memory
64498		FLDutchman	Robots (IOI13_robots)	C++14	100 / 100	2332 ms	44344 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;
int *weaks, *smalls, *W, *S;

int ok(int k){
    priority_queue<int> q;
    int i = 0;
    FOR(a, 0, A){
        int w = weaks[a];
        for(; i < T and W[i] < w; i++) q.push(S[i]);
        H(q.size());
        FOR(_, 0, k) {
            if(q.empty()) break;
            //cout << q.top() << endl;
            q.pop();
        }
    }
    for(; i < T; i++) q.push(S[i]);
    H(q.size());
    FOR(b, 0, B) {
        int s = smalls[b];
        FOR(_, 0, k){
            if(q.empty()) break;
            if(q.top() >= s) return 0;
            q.pop();
        }
    }
    return q.empty();
}

INT putaway(INT a, INT b, INT t, INT X[], INT Y[], INT w[], INT s[]) {
    W = w;
    S = s;
    A = a; B = b; T = t;
    weaks = X;
    smalls = Y;
    sort(weaks, weaks + A);
    sort(smalls, smalls + B, greater<int>());
    FOR(i, 0, T) toys.pb({W[i], S[i]});
    sort(toys.begin(), toys.end());
    FOR(i, 0, T) W[i] = toys[i].fst, S[i] = toys[i].snd;
    toys.clear();
    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;
}


/*
1 1 2
3
3
1 4
4 1


*/

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