Submission #18929

#	Time	Username	Problem	Language	Result	Execution time	Memory
18929		ggoh	Robots (IOI13_robots)	C++98	100 / 100	2176 ms	16400 KiB

robots

#include "robots.h"
#include<queue>
#include<algorithm>
int a,b,c,i,p,q,h,o,t,u;
struct AA{
    int x,y;
}data[1000002];
bool cmp(AA aa,AA bb){return aa.x<bb.x;}
std::priority_queue<int>P;
int putaway (int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    a=A;b=B;c=T;
    std::sort(X,X+a);
    std::sort(Y,Y+b);
    for(i=0;i<c;i++)
    {
        if((a==0||W[i]>=X[a-1])&&(b==0||S[i]>=Y[b-1]))
        {
            return -1;
        }
    }
    q=c;
    p=0;
    for(i=0;i<c;i++)data[i]={W[i],S[i]};
    std::sort(data,data+c,cmp);
    while(p!=q-1)
    {
        h=(p+q)/2;
        while(!P.empty())P.pop();
        o=0;
        for(i=0;i<a;i++)
        {
            while(o<c&&data[o].x<X[i])P.push(data[o].y),o++;
            t=h;
            while(t&&(!P.empty()))
            {
                P.pop();
                t--;
            }
        }
        while(o<c)P.push(data[o].y),o++;
        for(i=b-1;i>=0;i--)
        {
            if(P.empty())break;
            t=h;
            while(t&&(!P.empty()))
            {
                u=P.top();
                if(u<Y[i])
                {
                    t--;
                    P.pop();
                }
                else{i=0;break;}
            }
        }
        if(P.empty())q=h;
        else p=h;
    }
    return q;
}

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