Submission #56404

#	Time	Username	Problem	Language	Result	Execution time	Memory
56404		aquablitz11	Robots (IOI13_robots)	C++14	76 / 100	3050 ms	15716 KiB

robots

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

using pii = pair<int, int>;

const int N = 50010;
const int MT = 1000010;
const int INF = 2e9+1;

int A, B, T;
int *X, *Y, *W, *S, ix[MT], used[MT], tick=0;

bool check(int tim)
{
    ++tick;
    int tt = 0;
    // weak robot matching
    sort(ix, ix+T, [&] (int a, int b) {
        return W[a] < W[b];
    });
    int j = 0;
    priority_queue<pii> Q;
    for (int i = 0; i < A; ++i) {
        while (j < T && W[ix[j]] < X[i]) {
            Q.push({S[ix[j]], ix[j]});
            ++j;
        }
        for (int cnt = 0; cnt < tim && !Q.empty(); ++cnt) {
            used[Q.top().second] = tick;
            ++tt;
            Q.pop();
        }
    }

    // small robot matching
    sort(ix, ix+T, [&] (int a, int b) {
        return S[a] < S[b];
    });
    j = 0;
    while (!Q.empty()) Q.pop();
    for (int i = 0; i < B; ++i) {
        while (j < T && S[ix[j]] < Y[i]) {
            if (used[ix[j]] != tick)
                Q.push({W[ix[j]], ix[j]});
            ++j;
        }
        for (int cnt = 0; cnt < tim && !Q.empty(); ++cnt) {
            used[Q.top().second] = tick;
            ++tt;
            Q.pop();
        }
    }

    return tt == T;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    ::A = A, ::B = B, ::T = T, ::X = X, ::Y = Y, ::W = W, ::S = S;
    for (int i = 0; i < T; ++i)
        ix[i] = i;
    sort(X, X+A);
    sort(Y, Y+B);
    int b = 1, e = T+1;
    while (b < e) {
        int m = (b+e)/2;
        if (check(m))
            e = m;
        else
            b = m+1;
    }
    return b == T+1 ? -1 : b;
}

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