Submission #1190129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190129		raspy	Robots (IOI13_robots)	C++20	90 / 100	3095 ms	16484 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

vector<int> w, s, x, y;
vector<pair<int, int>> igrace;

bool mozno(int tr)
{
    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 < 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();
}

int putaway(int a, int b, int n, int X[], int Y[], int W[], int S[])
{
    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());
    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());
    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