제출 #962665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962665		NValchanov	로봇 (IOI13_robots)	C++17	0 / 100	2 ms	8648 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 sz < t.sz;
    }

};

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

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 mid;

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

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

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);
    sort(weak, weak + a, cmp);
    sort(small, small + b);

    return solve();
}

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