Submission #1208239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208239		Captain_Georgia	Robots (IOI13_robots)	C++20	100 / 100	1388 ms	32456 KiB

robots

#include "robots.h"

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

bool cmp1 (array<int, 3> x, array<int, 3> y) {
    return x[0] < y[0];
}
bool cmp2 (array<int, 3> x, array<int, 3> y) {
    return x[1] < y[1];
}

int putaway (int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X + A);
    sort(Y, Y + B);
    vector<array<int, 3>> arr(T);
    for (int i = 0;i < T;i ++) {
        if (W[i] >= X[A - 1] && S[i] >= Y[B - 1]) return -1;
        arr[i] = {W[i], S[i], i};
    }
    sort(arr.begin(), arr.end(), cmp1);
    // for (auto [x, y, z] : arr) cout << z << " ";
    // cout << "\n";
    // sort(arr.begin(), arr.end(), cmp2);
    // for (auto [x, y, z] : arr) cout << z << " ";
    // cout << "\n\n";
    
    vector<array<int, 3>> arr1 = arr;
    sort(arr1.begin(), arr1.end(), cmp1);
    vector<array<int, 3>> arr2 = arr;
    sort(arr2.begin(), arr2.end(), cmp2);

    int low = 1, high = T;
    while (low < high) {
        int mid = (low + high) / 2;

        vector<int> used(T, 0);
        priority_queue<array<int, 2>> pq;
        while (pq.size() > 0) pq.pop();
        for (int i = 0, l = 0;i < A;i ++) {
            while (l < T && X[i] > arr1[l][0]) {
                if (used[arr1[l][2]] == 0) pq.push({arr1[l][1], arr1[l][2]});
                l ++;
            }
            for (int j = 0;j < mid && pq.size() > 0;j ++) {
                used[pq.top()[1]] = 1;
                pq.pop();
            }
        }
        while (pq.size() > 0) pq.pop();
        for (int i = 0, l = 0;i < B;i ++) {
            while (l < T && Y[i] > arr2[l][1]) {
                if (used[arr2[l][2]] == 0) pq.push({arr2[l][0], arr2[l][2]});
                l ++;
            }
            for (int j = 0;j < mid && pq.size() > 0;j ++) {
                used[pq.top()[1]] = 1;
                pq.pop();
            }
        }
        int cnt = 0;
        for (int i = 0;i < T;i ++) cnt += used[i];

        if (cnt == T) high = mid;
        else low = mid + 1;
    }

    return high;
}

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