제출 #1080903

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

robots

#pragma GCC optimize("O3")
#include "robots.h"

#include <bits/stdc++.h>

#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; 
    set<pair<ll, ll>> cand;
    multiset<ll> usd;
    auto check = [&](ll x){
        slot_small.clear(); cand.clear();
        ll l=0; long long free_robot=0;
        for (ll i=0; i<T; i++){
            while (l<A and weak[l]>toy[i].ff) {
                l++; 
                free_robot+=x;
            }
            cand.insert({toy[i].ss, i});
            if (free_robot>0) free_robot--;
            else{
                slot_small.push_back((*cand.begin()).ss);
                cand.erase(cand.begin());
            }
        }
        sort(slot_small.rbegin(), slot_small.rend(), [&](ll op1, ll op2){
            return toy[op1].ss<toy[op2].ss;
        });
        l=0; usd.clear();
        for (ll i=0; i<(ll)(slot_small.size()); i++){
            while (l<B and small[l]>toy[slot_small[i]].ss){
                usd.insert(0);
                l++;
            }
            if (usd.empty()) return 0;
            ll val = *usd.begin();
            usd.erase(usd.begin());
            usd.insert(val+1);
        }
        if (usd.empty() or x>=*usd.rbegin()) return 1;
        return 0;
    };
    ll l=0, r=T;
    while (l+1<r){
        ll mid = l+(r-l)/2;
        if (check(mid)) r=mid;
        else l=mid;
    }
    if (check(r)) return r;
    else return -1;
}

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