Submission #93845

#	Time	Username	Problem	Language	Result	Execution time	Memory
93845		alexpetrescu	Robots (IOI13_robots)	C++14	100 / 100	928 ms	20344 KiB

robots

#include "robots.h"
#include <algorithm>

#define MAXN 50000
#define MAXT 1000000

int A, B, T, viz[MAXT];
int timp, S[MAXT], W[MAXT], ind1[MAXT], ind2[MAXT];
int heap[MAXN + 1], X[MAXN], Y[MAXN];
int unde[MAXT], poz[MAXT];

bool cmpS(const int &a, const int &b) {
    return S[a] < S[b];
}

bool cmpW(const int &a, const int &b) {
    return W[a] < W[b];
}

inline void urcare(int p) {
    while (p > 1 && W[heap[p]] > W[heap[p / 2]]) {
        std::swap(heap[p], heap[p / 2]);
        p /= 2;
    }
}

inline void coborare(int p) {
    int q;
    bool f = 1;
    while (f && (q = 2 * p) <= heap[0]) {
        if (q < heap[0] && W[heap[q + 1]] > W[heap[q]])
            q++;
        if (W[heap[q]] > W[heap[p]]) {
            std::swap(heap[p], heap[q]);
            p = q;
        } else
            f = 0;
    }
}

inline bool check(int k) {
    int p = 0, cnt = 0, q = 0;
    timp++;
    heap[0] = 0;
    for (int i = 0; i < B; i++) {
        while (p < T && S[ind2[p]] < Y[i])
            p++;
        if (p > 0 && unde[p - 1] == i) {
            heap[++heap[0]] = ind2[p - 1];
            urcare(heap[0]);
        }
        int u = k;
        while (heap[0] > 0 && u > 0) {
            viz[heap[1]] = timp;
            if (poz[heap[1]] == 0 || unde[poz[heap[1]] - 1] != unde[poz[heap[1]]]) {
                std::swap(heap[1], heap[heap[0]]);
                heap[0]--;
            } else
                heap[1] = ind2[poz[heap[1]] - 1];
            u--;
            cnt++;
            coborare(1);
        }
    }
    p = 0;
    for (int i = 0; i < A; i++) {
        while (p < T && W[ind1[p]] < X[i]) {
            q += viz[ind1[p]] != timp;
            p++;
        }
        if (q > k)
            q -= k, cnt += k;
        else {
            cnt += q;
            q = 0;
        }
    }
    return cnt == T;
}

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 = 0; i < A; i++)
        X[i] = x[i];
    for (int i = 0; i < B; i++)
        Y[i] = y[i];
    for (int i = 0; i < T; i++)
        ind1[i] = ind2[i] = i, W[i] = w[i], S[i] = s[i];
    std::sort(ind1, ind1 + T, cmpW);
    std::sort(ind2, ind2 + T, cmpS);
    std::sort(X, X + A);
    std::sort(Y, Y + b);
    bool ok = 1;
    for (int i = 0; i < T; i++)
        if ((A == 0 || W[i] >= X[A - 1]) && (B == 0 || S[i] >= Y[B - 1]))
            ok = 0;
    if (!ok)
        return -1;

    int p = 0;
    for (int i = 0; i < B; i++) {
        int sefu = p;
        while (p < T && S[ind2[p]] < Y[i]) {
            unde[p] = i;
            p++;
        }
        std::sort(ind2 + sefu, ind2 + p, cmpW);
        for (int j = sefu; j < p; j++)
            poz[ind2[j]] = j;
    }

    int rez = 0;
    for (int pas = 1 << 19; pas; pas >>= 1)
        if (!check(rez + pas))
            rez += pas;
    return rez + 1;
}

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