Submission #791154

#	Time	Username	Problem	Language	Result	Execution time	Memory
791154		Ronin13	Robots (IOI13_robots)	C++17	100 / 100	1348 ms	24684 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

int putaway(int A, int B, int T, int x[], int y[], int w[], int s[]) {
    vector <pii> vv;
    sort(x, x + A);
    sort(y, y + B);
    for(int i= 0; i < A; i++){
        vv.pb({x[i], -1});
    }
    for(int i = 0; i < T; i++){
        vv.pb({w[i], s[i]});
    }
    sort(vv.begin(), vv.end());
    int l = 0, r = T + 1;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        priority_queue <int> pq;
        for(auto to : vv){
            int x = to.s;
            if(x != -1) pq.push(x);
            else{
                int cur = 0;
                while(!pq.empty() && cur < mid){
                    pq.pop();
                    cur++;
                }
            }
        }
        for(int i = B - 1; i >= 0; i--){
            int cur = 0;
            while(cur < mid && !pq.empty()){
                int x = pq.top();
                if(x >= y[i]) break;
                pq.pop();
                cur++;
            }
        }
        pq.empty() ? r = mid : l = mid;
    }
    if(r == T + 1) r = -1;
    return r;
}

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