Submission #18924

#	Time	Username	Problem	Language	Result	Execution time	Memory
18924		ggoh	Robots (IOI13_robots)	C++98	76 / 100	3000 ms	29692 KiB

robots

#include "robots.h"
#include<set>
#include<algorithm>
int a,b,c,i,p,q,h,o,t;
struct AA{
    int x,y;
}data[1000002];
bool cmp(AA aa,AA bb){return aa.x<bb.x;}
std::multiset<int>s;
std::multiset<int>::iterator it;
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(!s.empty()){it=s.begin();s.erase(it);}
        o=0;
        for(i=0;i<a;i++)
        {
            while(o<c&&data[o].x<X[i])s.insert(data[o].y),o++;
            t=h;
            while(t&&(!s.empty()))
            {
                it=s.end();
                it--;
                s.erase(it);
                t--;
            }
        }
        while(o<c)s.insert(data[o].y),o++;
        for(i=0;i<b;i++)
        {
            t=h;
            while(t&&(!s.empty()))
            {
                it=s.begin();
                if((*it)<Y[i])
                {
                    t--;
                    s.erase(it);
                }
                else break;
            }
        }
        if(s.empty())q=h;
        else p=h;
    }
    return q;
}

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