Submission #1201946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201946		dosts	Robots (IOI13_robots)	C++20	0 / 100	73 ms	4932 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[]) {
    //A tane X limiti
    //B tane Y limiti
    //X limitlerine göre robotları sırala
    //sürekli k tane alabildiğin <=y robotları al
    vi robots(A),robots2(B);
    iota(all(robots),0ll);
    iota(all(robots2),0ll);
    sort(all(robots),[&](int x,int y) {
        return X[robots[x]] < X[robots[y]];
    });
    sort(all(robots2),[&](int x,int y) {
        return Y[robots2[x]] < Y[robots2[y]];
    });
    int32_t maxx = 0,maxy = 0;
    for (int i = 0;i<A;i++) maxx = max(maxx,X[i]);
    for (int i = 0;i<B;i++) maxy = max(maxy,Y[i]);
    for (int i = 0;i<T;i++) if (W[i] > maxx && S[i] > maxy) return -1;

    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;
    }
    return l;
}

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