Submission #7566

#	Time	Username	Problem	Language	Result	Execution time	Memory
7566		baneling100	Robots (IOI13_robots)	C++98	100 / 100	2132 ms	17804 KiB

robots

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

using namespace std;

pair <int,int> Toy[1000000];
int A, B, T, X[50000], Y[50000], Ans;

int OK(int Limit)
{
    priority_queue <int> Q;
    int i, j, k;

    j=0;
    for(i=0 ; i<A ; i++)
    {
        while(Toy[j].first<X[i] && j<T)
        {
            Q.push(Toy[j].second);
            j++;
        }
        for(k=1 ; k<=Limit ; k++)
        {
            if(Q.empty())
                break;
            Q.pop();
        }
    }
    for(i=j ; i<T ; i++)
        Q.push(Toy[i].second);
    if(Q.empty())
        return 1;
    for(i=B-1 ; i>=0 ; i--)
        for(j=1 ; j<=Limit ; j++)
        {
            if(Q.empty())
                return 1;
            k=Q.top();
            Q.pop();
            if(k>=Y[i])
                return 0;
        }
    if(Q.empty())
        return 1;
    return 0;
}

int putaway(int A_, int B_, int T_, int X_[], int Y_[], int W[], int S[])
{
    int i, Left, Mid, Right;

    A=A_;
    B=B_;
    T=T_;
    for(i=0 ; i<A ; i++)
        X[i]=X_[i];
    for(i=0 ; i<B ; i++)
        Y[i]=Y_[i];
    for(i=0 ; i<T ; i++)
        Toy[i]=make_pair(W[i],S[i]);
    sort(X,X+A);
    sort(Y,Y+B);
    sort(Toy,Toy+T);
    Left=1;
    Right=T;
    Ans=-1;
    while(Left<=Right)
    {
        Mid=(Left+Right)/2;
        if(OK(Mid))
        {
            Right=Mid-1;
            Ans=Mid;
        }
        else
            Left=Mid+1;
    }
    return Ans;
}

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