Submission #1183350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183350		alterio	Robots (IOI13_robots)	C++20	53 / 100	671 ms	34292 KiB

robots

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

#define all(x) (x).begin(), (x).end()

using namespace std;

int putaway(int A, int B, int T, int _X[], int _Y[], int W[], int S[]) {
    vector<pair<int, int>> T1, T2;
    for (int i = 0; i < T; i++) T1.push_back({W[i], i}), T2.push_back({S[i], i});
    sort(all(T1));
    reverse(all(T1));
    sort(all(T2));
    reverse(all(T2));
    vector<int> X, Y;
    for (int i = 0; i < A; i++) X.push_back(_X[i]);
    for (int i = 0; i < B; i++) Y.push_back(_Y[i]);
    sort(all(X));
    reverse(all(X));
    sort(all(Y));
    reverse(all(Y));
    bool done[T];
    memset(done, 0, sizeof(done));
    int mxX = 0, mxY = 0;
    for (int i = 0; i < A; i++) mxX = max(mxX, X[i]);
    for (int i = 0; i < B; i++) mxY = max(mxY, Y[i]);
    for (int i = 0; i < T; i++) {
        if (W[i] >= mxX && S[i] >= mxY) return -1;
    }
    vector<int> left;
    for (int i = 0; i < T; i++) left.push_back(i);
    for (int ans = 1; ; ans++) {
        vector<pair<int, int>> valsX, valsY;
        for (auto x : left) {
            if (W[x] >= mxX) valsY.push_back({S[x], x});
            if (S[x] >= mxY) valsX.push_back({W[x], x});
        }
        unordered_set<int> usedX, usedY;
        int ptrV = 0, ptr = 0;
        sort(all(valsX));
        reverse(all(valsX));
        sort(all(valsY));
        reverse(all(valsY));
        while (ptrV < valsX.size() && ptr < X.size()) {
            if (X[ptr] <= valsX[ptrV].first) {
                ptrV++;
                continue;
            }
            int ind = valsX[ptrV].second; 
            done[ind] = 1;
            usedX.insert(ptr);
            ptr++;
            ptrV++;
        }
        ptrV = ptr = 0;
        while (ptrV < valsY.size() && ptr < Y.size()) {
            if (Y[ptr] <= valsY[ptrV].first) {
                ptrV++;
                continue;
            }
            int ind = valsY[ptrV].second;
            done[ind] = 1;
            usedY.insert(ptr);
            ptr++;
            ptrV++;
        }
        ptr = 0;
        for (auto x : T1) {
            if (done[x.second]) continue;
            while (usedX.count(ptr)) ptr++;
            if (ptr >= X.size()) break;
            if (x.first < X[ptr]) {
                done[x.second] = 1;
                usedX.insert(ptr);
            }
        }
        ptr = 0;
        for (auto x : T2) {
            if (done[x.second]) continue;
            while (usedY.count(ptr)) ptr++;
            if (ptr >= Y.size()) break;
            if (x.first < Y[ptr]) { 
                done[x.second] = 1;
                usedY.insert(ptr);
            }
        }

        vector<int> newLeft;
        for (auto x : left) {
            if (!done[x]) newLeft.push_back(x);
        }
        left = newLeft;
        vector<pair<int, int>> newT1, newT2;
        for (auto x : T1) {
            if (!done[x.second]) newT1.push_back(x);
        }
        for (auto x : T2) {
            if (!done[x.second]) newT2.push_back(x);
        }
        T1 = newT1, T2 = newT2;
        if (!left.size()) return ans;
    }
}

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