Submission #1008686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008686		jer033	Robots (IOI13_robots)	C++17	100 / 100	1337 ms	28824 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

pii flip(pii values)
{
    return {values.second, values.first};
}

//IMPORTANT NOTE: The robot can carry the toy if its weight/size is STRICTLY LESS than the limit
bool query(int D, vector<int> (&x), vector<int> (&y), vector<pii> (&toys))
{
    priority_queue<pii> toystash;
    int A = x.size();
    int B = y.size();
    int toy_index = 0;
    for (int i=0; i<A; i++)
    {
        //process the weak robots from weakest to strongest
        while (x[i] > toys[toy_index].first)
        {
            toystash.push(flip(toys[toy_index]));
            toy_index++;
        }
        int cleaned = 0;
        while ((cleaned<D) and (!toystash.empty()))
        {
            toystash.pop();
            cleaned++;
        }
    }
    int total_toys = toys.size()-2;
    while (toy_index<=total_toys)
    {
        toystash.push(flip(toys[toy_index]));
        toy_index++;
    }
    for (int i=B-1; i>=0; i--)
    {
        //process the small robots from biggest to smallest, yes, reverse order from previous
        int cleaned = 0;
        while ((cleaned<D) and (!toystash.empty()))
        {
            pii next_toy = toystash.top();
            if (next_toy.first < y[i])
            {
                toystash.pop();
                cleaned++;
            }
            else
            {
                cleaned = D;
            }
        }
    }
    if (toystash.empty())
        return 1;
    return 0;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    vector<int> x;
    vector<int> y;
    x.reserve(A);
    y.reserve(B);
    for (int i=0; i<A; i++)
        x.push_back(X[i]);
    for (int i=0; i<B; i++)
        y.push_back(Y[i]);
    int max_weight = 0;
    if (A)
        max_weight = X[A-1];
    int max_size = 0;
    if (B)
        max_size = Y[B-1];
    
    vector<pii> toys;
    toys.reserve(T+1);
    for (int i=0; i<T; i++)
    {
        toys.push_back({W[i], S[i]});
        if ((W[i]>=max_weight) and (S[i]>=max_size))
            return -1;
    }
    sort(toys.begin(), toys.end());
    toys.push_back({max_weight, max_size});//add an inaccessible toy to help the implementation

    int lo = 1;
    int hi = T;
    while (lo!=hi)
    {
        int mid = (lo+hi)/2;
        if (query(mid, x, y, toys))
            hi = mid;
        else
            lo = mid+1;
    }
    return lo;
}

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