Submission #1201954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201954		dosts	Robots (IOI13_robots)	C++20	100 / 100	1353 ms	17440 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

int32_t putaway(int32_t A, int32_t B, int32_t T, int32_t X[], int32_t Y[], int32_t W[], int32_t S[]) {
    vi robots(A),robots2(B);
    iota(all(robots),0ll);
    iota(all(robots2),0ll);
    sort(all(robots),[&](int x,int y) {
        return X[x] < X[y];
    });
    sort(all(robots2),[&](int x,int y) {
        return Y[x] < Y[y];
    });
    vi toys(T);
    iota(all(toys),0ll);
    sort(all(toys),[&](int x,int y) {
        return W[x] < W[y];
    });
    auto check = [&](int k) -> bool {
        int ptr = 0;
        priority_queue<int> pq;
        for (int i = 0;i<A;i++) {
            while (ptr < T && W[toys[ptr]] < X[robots[i]]) {
                pq.push(S[toys[ptr]]);
                ptr++;
            }
            int rem = k;
            while (!pq.empty() && rem) {
                pq.pop();
                rem--;
            }
        }
        while (ptr < T) {
            pq.push(S[toys[ptr]]);
            ptr++;
        }
        for (int i = B-1;i>=0;i--) {
            int rem = k;
            while (!pq.empty() && rem) {
                if (pq.top() >= Y[robots2[i]]) return false;
                pq.pop();
                rem--;
            }
        }
        return (pq.empty());
    };
    int l = 1;
    int r = T;
    while (l<=r) {
        int m = (l+r) >> 1;
        if (check(m)) r = m-1;
        else l = m+1;
    }
    if (l == T+1) return -1;
    return l;
}

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