Submission #957518

#	Time	Username	Problem	Language	Result	Execution time	Memory
957518		vjudge1	Robots (IOI13_robots)	C++17	53 / 100	287 ms	22052 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> berat, ukuran;
    for(i = 0; i < T; i++)
    {
        berat.push_back({W[i], i});
        ukuran.push_back({S[i], i});
    }
    sort(berat.begin(), berat.end());
    sort(ukuran.begin(), ukuran.end());

    int l = 1, r = T, ans = -1;
    vector<bool> udah(T+5);
    while(l <= r)
    {
        int mid = (l+r)/2;
        for(i = 0; i < T; i++) udah[i] = 0;

        int res = 0, res2 = 0, bts = 0;
        for(i = 0, j = 0; i < T and j < A;)
        {
            int val = berat[i].fi, id = berat[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(X[j] > val)
            {
                ++res;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        bts = 0;
        for(i = 0, j = 0; i < T and j < B;)
        {
            int val = ukuran[i].fi, id = ukuran[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(Y[j] > val)
            {
                ++res;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        
        for(i = 0; i < T; i++) udah[i] = 0;
        bts = 0;
        for(i = 0, j = 0; i < T and j < B;)
        {
            int val = ukuran[i].fi, id = ukuran[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(Y[j] > val)
            {
                ++res2;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }
        bts = 0;
        for(i = 0, j = 0; i < T and j < A;)
        {
            int val = berat[i].fi, id = berat[i].se;
            if(udah[id])
            {
                ++i;
                continue;
            }
            if(bts == mid)
            {
                ++j;
                bts = 0;
                continue;
            }
            if(X[j] > val)
            {
                ++res2;
                ++bts;
                udah[id] = 1;
                ++i;
            }
            else
            {
                ++j;
                bts = 0;
            }
        }


        if(res == T or res2 == 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];
//     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: 0 / 37
• Subtask 5: 0 / 10