제출 #1113234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113234		Gray	로봇 (IOI13_robots)	C++17	100 / 100	1407 ms	26120 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>
#include <queue>

#define ll int
#define ff first
#define ss second
#define ln "\n"

using namespace std;


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<ll> weak(A), small(B);
    vector<pair<ll, ll>> toy(T);
    for (ll i=0; i<A; i++){
        weak[i]=X[i];
    }
    for (ll i=0; i<B; i++){
        small[i]=Y[i];
    }
    for (ll i=0; i<T; i++){
        toy[i] = {W[i], S[i]};
    }
    sort(weak.rbegin(), weak.rend());
    sort(small.rbegin(), small.rend());
    sort(toy.rbegin(), toy.rend());
    vector<ll> slot_small;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> cand;
    ll lo=T/(A+B)-1, hi=T+1;
    bool upos=0;
    while (lo+1<hi){
        ll x = lo+(hi-lo)/2;
        bool pos=1;
        slot_small.clear();
        while (!cand.empty()) cand.pop();
        ll l=0; int free_robot=0;
        for (ll i=0; i<T; i++){
            while (l<A and weak[l]>toy[i].ff) {
                l++;
                if (INT_MAX-free_robot<x) free_robot=INT_MAX;
                else free_robot+=x;
            }
            cand.push({toy[i].ss, i});
            if (free_robot>0) free_robot--;
            else{
                slot_small.emplace_back(cand.top().ss);
                cand.pop();
            }
        }
        sort(slot_small.rbegin(), slot_small.rend(), [&](ll op1, ll op2){
            return toy[op1].ss<toy[op2].ss;
        });
        l=0; free_robot=0;
        for (ll i=0; i<(ll)(slot_small.size()); i++){
            while (l<B and small[l]>toy[slot_small[i]].ss){
                free_robot+=x;
                l++;
            }
            if (free_robot==0) pos=0;
            else free_robot--;
        }
        if (pos) {hi=x; upos=1;}
        else lo=x;
    }
    if (upos) return hi;
    else return -1;
}

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