Submission #204016

#	Time	Username	Problem	Language	Result	Execution time	Memory
204016		Andrei_Cotor	Robots (IOI13_robots)	C++14	100 / 100	2418 ms	32392 KiB

robots

#include<robots.h>
#include<queue>
#include<algorithm>

using namespace std;

pair<int,int> RW[1000005];
pair<int,int> RS[1000005];
bool Rem[1000005];

bool possible(int sec, int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    for(int i=0; i<T; i++)
        Rem[i]=0;

    //robotii weak
    priority_queue<pair<int,int> > Q;
    int ind=1;
    for(int i=0; i<A; i++)
    {
        while(ind<=T && X[i]>RW[ind].first)
        {
            Q.push({S[RW[ind].second],RW[ind].second});
            ind++;
        }

        for(int j=1; j<=sec; j++)
        {
            if(Q.empty())
                break;
            Rem[Q.top().second]=1;
            Q.pop();
        }
    }

    //robotii small
    deque<int> Q2;
    ind=1;
    for(int i=0; i<B; i++)
    {
        while(ind<=T && Y[i]>RS[ind].first)
        {
            if(!Rem[RS[ind].second])
                Q2.push_back(RS[ind].second);
            ind++;
        }

        for(int j=1; j<=sec; j++)
        {
            if(Q2.empty())
                break;
            Rem[Q2.front()]=1;
            Q2.pop_front();
        }
    }

    for(int i=0; i<T; i++)
        if(!Rem[i])
            return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    for(int i=1; i<=T; i++)
    {
        RW[i]={W[i-1],i-1};
        RS[i]={S[i-1],i-1};
    }

    sort(RW+1,RW+T+1);
    sort(RS+1,RS+T+1);
    sort(X,X+A);
    sort(Y,Y+B);

    int rez=0;
    for(int i=19; i>=0; i--)
        if(!possible(rez+(1<<i),A,B,T,X,Y,W,S))
            rez+=(1<<i);
    rez++;
    if(rez>T)
        rez=-1;
    return rez;
}

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