Submission #945624

#	Time	Username	Problem	Language	Result	Execution time	Memory
945624		vjudge1	Robots (IOI13_robots)	C++17	76 / 100	172 ms	25552 KiB

robots

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

using namespace std;

#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

vector<pii> els;
vector<int> rB;
vector<int> pos;
int n, a, b;

bool check(int x)
{
    vector<int> can(n);
    priority_queue<int> cur, els2;

    int canBeDeleted = 0, extra = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        cur.push(-els[i].s);
        canBeDeleted += pos[i] * x;
        if (n - i > canBeDeleted + extra)
        {
            extra++;
            els2.push(-cur.top());
            cur.pop();
        }
        assert(n - i <= canBeDeleted + extra);
    }
    for (int i = 0; i < b; ++i)
    {
        if (!els2.size())
            break;
        if (els2.top() >= rB[i])
            return 0;
        for (int j = 0; j < x; ++j)
        {
            if (els2.size() == 0)
                break;
            els2.pop();
        }
    }

    return els2.size() == 0;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    n = T;
    a = A;
    b = B;
    int L = 0, R = n + 1;

    for (int i = 0; i < B; ++i)
    {
        rB.pb(Y[i]);
    }
    sort(all(rB));
    reverse(all(rB));

    for (int i = 0; i < n; ++i)
    {
        els.pb({W[i], S[i]});
    }
    sort(all(els));

    pos.resize(T);
    for (int i = 0; i < a; ++i)
    {
        auto it = lower_bound(all(els), make_pair(X[i], 0)) - els.begin();
        if (it)
            pos[it - 1]++;
    }

    while (R - L > 1)
    {
        int M = (L + R) >> 1;
        if (check(M))
            R = M;
        else
            L = M;
    }
    if (R == n + 1)
        return -1;
    else
        return R;
}

// /////////////////

// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include "robots.h"

// #define MAX_A 50000
// #define MAX_B 50000
// #define MAX_T 500000

// static int X[MAX_A];
// static int Y[MAX_B];
// static int W[MAX_T];
// static int S[MAX_T];

// int main()
// {
//     int A, B, T, i;

//     assert(scanf("%d", &A) == 1);
//     assert(scanf("%d", &B) == 1);
//     assert(scanf("%d", &T) == 1);

//     for (i = 0; i < A; i++)
//         assert(scanf("%d", &X[i]) == 1);
//     for (i = 0; i < B; i++)
//         assert(scanf("%d", &Y[i]) == 1);
//     for (i = 0; i < T; i++)
//         assert(scanf("%d%d", &W[i], &S[i]) == 2);

//     int answer = putaway(A, B, T, X, Y, W, S);

//     printf("%d\n", answer);

//     return 0;
// }

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