Submission #1190126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190126		raspy	Robots (IOI13_robots)	C++20	90 / 100	3093 ms	16412 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

// w -> teze igrac, s - > velikosti igrac
// x -> omejitve dviga teze, y -> omejitve dviga velikosti

int putaway(int a, int b, int n, int X[], int Y[], int W[], int S[])
{
    vector<int> w, s, x, y;
    for (int i = 0; i < n; i++)
    {
        w.push_back(W[i]);
        s.push_back(S[i]);
    }
    for (int i = 0; i < a; i++)
        x.push_back(X[i]);
    for (int i = 0; i < b; i++)
        y.push_back(Y[i]);
    sort(y.begin(), y.end());
    sort(x.begin(), x.end());
    vector<pair<int, int>> igrace;
    for (int i = 0; i < n; i++)
        igrace.push_back(make_pair(w[i], s[i]));
    sort(igrace.begin(), igrace.end());
    reverse(y.begin(), y.end());
    auto mozno = [&igrace, &x, &y](int tr) -> bool
    {
        int j = 0;
        priority_queue<int> st;
        for (int v : x)
        {
            while (j < igrace.size() && igrace[j].first < v)
            {
                st.push(igrace[j].second);
                j++;
            }
            for (int i = 0; i < tr && st.size(); i++)
                st.pop();
        }
        while (j < (int)igrace.size())
        {
            st.push(igrace[j].second);
            j++;
        }
        for (int v : y)
        {
            for (int i = 0; i < tr && st.size(); i++)
                if (st.top() < v)
                    st.pop();
        }
        return st.empty();
    };
    if (!mozno(n+1))
        return -1;
    int l = -1, d = n;
    while (l+1 < d)
    {
        int mid = (l+d)/2;
        if (mozno(mid))
            d = mid;
        else
            l = mid;
    }
    return d;
}

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