Submission #1271112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271112		thuhienne	Robots (IOI13_robots)	C++20	100 / 100	1329 ms	15008 KiB

robots

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

static int A, B, T;
static int robot1[50009], robot2[50009];
static pair<int,int> toys[1000009];

bool check(int lim) {
    priority_queue<int> pq;
    int pt = 1;

    // phase 1: robots yếu
    for (int i = 1; i <= A; i++) {
        while (pt <= T && toys[pt].first <= robot1[i]) {
            pq.push(toys[pt].second);
            pt++;
        }
        for (int j = 1; j <= lim; j++) {
            if (pq.empty()) break;
            pq.pop();
        }
    }

    // phase 2: gom toys còn lại
    while (pt <= T) {
        pq.push(toys[pt].second);
        pt++;
    }

    vector<int> leftover;
    while (!pq.empty()) {
        leftover.push_back(pq.top());
        pq.pop();
    }
    sort(leftover.begin(), leftover.end());

    int idx = 0;
    for (int i = 1; i <= B; i++) {
        for (int j = 1; j <= lim; j++) {
            if (idx < (int)leftover.size() && leftover[idx] <= robot2[i]) {
                idx++;
            } else break;
        }
    }
    return idx == (int)leftover.size();
}

int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
    A = a;
    B = b;
    T = t;

    for (int i = 1; i <= A; i++) robot1[i] = X[i-1];
    for (int i = 1; i <= B; i++) robot2[i] = Y[i-1];
    for (int i = 1; i <= T; i++) {
        toys[i].first = W[i-1] + 1;
        toys[i].second = S[i-1] + 1;
    }

    sort(robot1 + 1, robot1 + 1 + A);
    sort(robot2 + 1, robot2 + 1 + B);
    sort(toys + 1, toys + 1 + T);

    int l = 1, r = T, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

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