Submission #962675

#	Time	Username	Problem	Language	Result	Execution time	Memory
962675		NValchanov	Robots (IOI13_robots)	C++17	100 / 100	1618 ms	31516 KiB

robots

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

using namespace std;
typedef long long ll;

const ll MAXT = 1e6 + 10;
const ll MAXA = 5e4 + 10;
const ll MAXB = 5e4 + 10;

struct toy
{
    ll sz;
    ll w;

    toy(){};
    toy(ll _w, ll _sz)
    {
        w = _w;
        sz = _sz;
    }

    bool operator<(const toy&t)const
    {
        return w < t.w;
    }

};

bool cmp(ll a, ll b)
{
    return a > b;
}

bool cmp_t(toy t1, toy t2)
{
    return t1.sz < t2.sz;
}

ll t,a,b;
ll weak[MAXA];
ll small[MAXB];
toy toys[MAXT];

bool check(ll k)
{
    priority_queue < toy > pq;
    ll ptr = 0;

    for(int i = 0; i < b; i++)
    {
        while(ptr < t && toys[ptr].sz < small[i])
        {
            pq.push(toys[ptr]);
            ptr++;
        }
        for(int j = 1; j <= k; j++)
        {
            if(pq.empty())
                break;

            pq.pop();
        }
    }

    while(ptr < t)
    {
        pq.push(toys[ptr]);
        ptr++;
    }

    for(int i = 0; i < a; i++)
    {
        if(pq.empty())
            break;

        if(pq.top().w >= weak[i])
            return false;

        for(int j = 1; j <= k; j++)
        {
            if(pq.empty())
                break;

            pq.pop();
        }
    }

    return pq.empty();
}

int solve()
{
    ll left = 0;
    ll right = t + 1;
    ll ans = t + 1;
    ll mid;

    while(left <= right)
    {
        mid = (left + right) / 2;
        if(check(mid))
        {
            right = mid - 1;
            ans = mid;
        }
        else
            left = mid + 1;
    }

    return ans == t + 1 ? -1 : ans;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    t = T;
    a = A;
    b = B;

    for(int i = 0; i < t; i++)
    {
        toys[i] = toy(W[i], S[i]);
    }

    for(int i = 0; i < a; i++)
    {
        weak[i] = X[i];
    }
    for(int i = 0; i < b; i++)
    {
        small[i] = Y[i];
    }

    sort(toys, toys + t, cmp_t);
    sort(weak, weak + a, cmp);
    sort(small, small + b);

    return solve();
}

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