Submission #1089681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089681		raphaelp	Robots (IOI13_robots)	C++14	0 / 100	1 ms	348 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int solve(int m, vector<int> &WR, vector<int> &SR, vector<pair<int, int>> &Tab)
{
    int N = Tab.size();
    vector<int> occ(N);
    int buff = N - 1;
    for (int i = WR.size() - 1; i >= 0; i--)
    {
        int left = m;
        while (buff >= 0 && Tab[buff].first >= WR[i])
            buff--;
        while (left && buff >= 0)
        {
            occ[buff] = 1;
            left--;
            buff--;
        }
    }
    priority_queue<int> PQ;
    vector<int> remain;
    for (int i = N - 1; i >= 0; i--)
    {
        PQ.push(-Tab[i].second);
        if (occ[i] == 0)
        {
            remain.push_back(-PQ.top());
            PQ.pop();
        }
    }
    sort(remain.begin(), remain.end());
    buff = remain.size() - 1;
    for (int i = SR.size() - 1; i >= 0; i--)
    {
        int left = m;
        if (buff >= 0 && remain[buff] >= SR[i])
            return 0;
        while (left && buff >= 0)
        {
            buff--;
            left--;
        }
    }
    return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    vector<int> WR(A), SR(B);
    for (int i = 0; i < A; i++)
        WR[i] = X[i];
    for (int i = 0; i < B; i++)
        SR[i] = Y[i];
    sort(WR.begin(), WR.end());
    sort(SR.begin(), SR.end());
    vector<pair<int, int>> Tab;
    for (int i = 0; i < T; i++)
    {
        Tab.push_back({W[i], S[i]});
    }
    sort(Tab.begin(), Tab.end());
    int L = 1, R = T + 1;
    while (L != R)
    {
        int m = (L + R) / 2;
        if (solve(m, WR, SR, Tab))
            R = m;
        else
            L = m + 1;
    }
    if (L == T + 1)
        return -1;
    return L;
}
/*int main()
{
    int A, B, T;
    cin >> A >> B >> T;
    int X[A], Y[B], W[T], S[T];
    for (int i = 0; i < A; i++)
        cin >> X[i];
    for (int i = 0; i < B; i++)
        cin >> Y[i];
    for (int i = 0; i < T; i++)
        cin >> W[i] >> S[i];
    cout << putaway(A, B, T, X, Y, W, S);
}*/

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