Submission #107226

#	Time	Username	Problem	Language	Result	Execution time	Memory
107226		nickyrio	Robots (IOI13_robots)	C++17	100 / 100	1914 ms	24380 KiB

robots

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

using namespace std;

bool canPut(int TIME, int A, int B, int T, vector< vector<int> >& WeakRobot, int Y[], int S[]) {
    priority_queue<int> maxSize;
    for (int i = 0; i < A; ++i) {
        int sz = WeakRobot[i].size();
        if (TIME < sz) {
            for (int j = TIME; j < sz; ++j) {
                maxSize.push(S[WeakRobot[i][j]]);
   //             cerr << "+ " << S[WeakRobot[i][j]] << endl; 
            }
        } else {
            while (sz < TIME && !maxSize.empty()) {
                ++sz;
  //              cerr << "- " << maxSize.top() << endl;
                maxSize.pop();
            }
        }
    }
    for (int val : WeakRobot[A]) maxSize.push(S[val]);
    
    int i = B - 1, sz = maxSize.size();
    while (i >= 0 && sz) {
 //       cerr << i << ' ' << sz << endl;
        int j = min(sz, TIME);
 //       cerr << "Small Robot " << i << endl;
        sz -= j;
        while (j--) {
 //           cerr << maxSize.top() << ' ';
            if (maxSize.top() > Y[i]) return false;
            maxSize.pop();
        }
 //       cerr << endl;
        --i;
    }
    return (sz == 0);
}

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< vector<int> > WeakRobot(A + 1);
    for (int i = 0; i < T; ++i) {
        ++W[i], ++S[i];
        int idW = lower_bound(X, X + A, W[i]) - X;
        WeakRobot[idW].push_back(i);
    }
    for (int i = 0; i < A; ++i) {
        sort(WeakRobot[i].begin(), WeakRobot[i].end(), [&](int x, int y) {
            return S[x] > S[y];
        });
    }
/*
    for (int i = 0; i <= A; ++i) {
        cerr << "WeakRobot " << i << endl;
        for (int val : WeakRobot[i]) cerr << S[val] << ' '; cerr << endl;
    }
*/
    int l = 1, r = T;
    int ans = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (canPut(m, A, B, T, WeakRobot, Y, S)) {
            ans = m;
            r = m - 1;
        } else l = m + 1;
    }

    return ans;
}

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