Submission #957544

#	Time	Username	Problem	Language	Result	Execution time	Memory
957544		IsaL	Robots (IOI13_robots)	C++17	100 / 100	1342 ms	19280 KiB

robots

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

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll N = 200069;
const ll mod = 1e9 + 7;

int tc;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int i, j;
    sort(X, X+A);
    sort(Y, Y+B);

    vector<pii> sim;
    for(i = 0; i < T; i++)
    {
        sim.push_back({W[i], S[i]});
    }
    sort(sim.begin(), sim.end());

    int l = 1, r = T, ans = -1;
    vector<bool> udah(T+5);
    while(l <= r)
    {
        int mid = (l+r)/2;
        
        int res = 0;
        priority_queue<int> pq;
        for(i = 0, j = 0; i < A; i++)
        {
            while(j < T and sim[j].fi < X[i])
            {
                pq.push(sim[j].se);
                ++j;
            }

            int bts = mid;
            while(!pq.empty() and bts > 0)
            {
                ++res;
                --bts;
                pq.pop();
            }
        }

        while(j < T)
        {
            pq.push(sim[j].se);
            ++j;
        }

        for(i = B-1; i >= 0; i--)
        {
            int bts = mid;
            while(!pq.empty() and bts > 0 and Y[i] > pq.top())
            {
                ++res;
                --bts;
                pq.pop();
            }
        }

        if(res == T)
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    return ans;
}

// int main()
// {
//     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//     int i, j;

//     int A, B, T;
//     cin >> A >> B >> T;
//     int X[A], Y[B], W[T], S[T];
//     for(i = 0; i < A; i++) cin >> X[i];
//     for(i = 0; i < B; i++) cin >> Y[i];
//     for(i = 0; i < T; i++) cin >> W[i] >> S[i];
//     // for(i = 0; i < T; i++) cin >> S[i];

//     cout << putaway(A, B, T, X, Y, W, S) << '\n';
// }

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