Submission #467444

#	Time	Username	Problem	Language	Result	Execution time	Memory
467444		SirCovidThe19th	Robots (IOI13_robots)	C++17	100 / 100	1900 ms	24352 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std; 

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    pair<int, int> toys[T];
    for (int i = 0; i < T; i++) toys[i] = {W[i], S[i]};
    sort(X, X + A); sort(Y, Y + B); sort(toys, toys + T); 

    auto check = [&](int mid){
        priority_queue<int> pq; int pt = 0;
        for (int i = 0; i < A; i++){
            for (; pt < T and toys[pt].first < X[i]; pt++) pq.push(toys[pt].second);
            for (int j = 0; j < mid and !pq.empty(); j++) pq.pop();
        }
        for (; pt < T; pt++) pq.push(toys[pt].second);
        for (int i = B - 1; i >= 0; i--){
            for (int j = 0; j < mid and !pq.empty() and pq.top() < Y[i]; j++) pq.pop();
        }
        return pq.empty();
    };
    
    int low = 1, high = T;
    while (low < high){
        int mid = (low + high) / 2;
        check(mid) ? high = mid : low = mid + 1;
    }
    return check(high) ? high : -1;
}

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