Submission #884847

#	Time	Username	Problem	Language	Result	Execution time	Memory
884847		maxFedorchuk	Robots (IOI13_robots)	C++14	100 / 100	1437 ms	39468 KiB

robots

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

using namespace std;

const long long MX=5e4+10;
const long long INF=1e18;
const long long MX2=1e6;

pair < long long , long long > toys[MX2];
long long lgk[MX];
long long sml[MX];

vector < long long > forlgk[MX];

long long kw,ks,t;

bool chk(long long k)
{
    priority_queue < long long > knd;

    for(long long i=1;i<=kw;i++)
    {
        for(auto u:forlgk[i])
        {
            knd.push(u);
        }

        long long vd=0;
        while(!knd.empty() && vd<k)
        {
            knd.pop();
            vd++;
        }
    }

    for(auto u:forlgk[kw+1])
    {
        knd.push(u);
    }

    for(long long i=ks;i>=1;i--)
    {
        long long vd=0;

        while(!knd.empty() && vd<k)
        {
            if(knd.top()>=sml[i])
            {
                return 0;
            }

            knd.pop();
            vd++;
        }
    }

    return knd.empty();
}


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

    for(long long i=1;i<=kw;i++)
    {
        lgk[i]=X[i-1];
    }

    for(long long i=1;i<=ks;i++)
    {
        sml[i]=Y[i-1];
    }

    sort(lgk+1,lgk+kw+1);
    sort(sml+1,sml+ks+1);
    lgk[kw+1]=INF;

    for(long long i=1;i<=t;i++)
    {
        toys[i].first=W[i-1];
        toys[i].second=S[i-1];
    }

    sort(toys+1,toys+1+t);

    long long uk=1;
    for(long long i=1;i<=t;i++)
    {
        while(lgk[uk]<=toys[i].first)
        {
            uk++;
        }

        forlgk[uk].push_back(toys[i].second);
    }

    long long l=0,r=t+1;

    while((l+1)<r)
    {
        long long mid=(l+r)/2;

        if(chk(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }

    if(chk(r))
    {
        return r;
    }
    else
    {
        return -1;
    }
}

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