Submission #1080927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080927		Gray	Robots (IOI13_robots)	C++17	76 / 100	3095 ms	37824 KiB

robots

#pragma GCC optimize("O3")
#pragma GCC target("sse3")
#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;
    ll lo=0, hi=T+1;
    bool upos=0;
    while (lo+1<hi){
        ll x = lo+(hi-lo)/2;
        bool pos=1;
        slot_small.clear(); cand.clear();
        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.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; 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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10