Submission #426789

#	Time	Username	Problem	Language	Result	Execution time	Memory
426789		Aldas25	Robots (IOI13_robots)	C++14	100 / 100	1865 ms	24888 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;

const int MAXN = 1000100;

int a, b, t;
vi x, y;
vii toys;
//bool taken[MAXN];

bool check (int k) {
    priority_queue<int> q;

    int tId = 0;
    FOR(i, 0, a-1) {
        while (tId < t && toys[tId].f < x[i]) {
            q.push(toys[tId].s);
            tId++;
        }

        REP(k) {
            if (q.empty()) break;
            q.pop();
        }
    }
    while (tId < t) {
        q.push(toys[tId].s);
        tId++;
    }

    FOR(i, 0, b-1) {
        REP(k) {
            if (q.empty()) break;
            if (q.top() >= y[i]) break;
            q.pop();
        }
    }

    if (q.empty()) return true;
    else return false;
}

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-1) x.pb(X[i]);
    FOR(i, 0, b-1) y.pb(Y[i]);
    FOR(i, 0, t-1) toys.pb({W[i], S[i]});

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    reverse(y.begin(), y.end());
    sort(toys.begin(), toys.end());

    FOR(i, 0, t-1) if ((a == 0 || W[i] >= x[a-1]) && (b == 0 || S[i] >= y[0])) return -1;

    int le = 0, ri = t;
    while (le < ri) {
        int mid = (le+ri)/2;
        if (check(mid)) ri = mid;
        else le = mid+1;
    }

    return le;
}

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