oj.uz

Submission #18929

# Submission time Handle Problem Language Result Execution time Memory
18929 2016-02-16T13:01:18 Z ggoh Robots (IOI13_robots) C++
100 / 100
 2176 ms 16400 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13324 KB Output is correct
2 Correct 0 ms 13324 KB Output is correct
3 Correct 0 ms 13324 KB Output is correct
4 Correct 0 ms 13324 KB Output is correct
5 Correct 0 ms 13324 KB Output is correct
6 Correct 0 ms 13324 KB Output is correct
7 Correct 0 ms 13324 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13324 KB Output is correct
2 Correct 0 ms 13324 KB Output is correct
3 Correct 0 ms 13324 KB Output is correct
4 Correct 1605 ms 16400 KB Output is correct
5 Correct 238 ms 13324 KB Output is correct
6 Correct 43 ms 13324 KB Output is correct
7 Correct 679 ms 14864 KB Output is correct
8 Correct 1083 ms 16400 KB Output is correct
9 Correct 2116 ms 16400 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13324 KB Output is correct
2 Correct 0 ms 13324 KB Output is correct
3 Correct 0 ms 13324 KB Output is correct
4 Correct 0 ms 13324 KB Output is correct
5 Correct 0 ms 13324 KB Output is correct
6 Correct 0 ms 13324 KB Output is correct
7 Correct 0 ms 13324 KB Output is correct
8 Correct 0 ms 13324 KB Output is correct
9 Correct 0 ms 13324 KB Output is correct
10 Correct 0 ms 13324 KB Output is correct
11 Correct 0 ms 13324 KB Output is correct
12 Correct 0 ms 13324 KB Output is correct
13 Correct 0 ms 13324 KB Output is correct
14 Correct 0 ms 13324 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13324 KB Output is correct
2 Correct 0 ms 13324 KB Output is correct
3 Correct 0 ms 13324 KB Output is correct
4 Correct 0 ms 13324 KB Output is correct
5 Correct 0 ms 13324 KB Output is correct
6 Correct 0 ms 13324 KB Output is correct
7 Correct 0 ms 13324 KB Output is correct
8 Correct 0 ms 13324 KB Output is correct
9 Correct 0 ms 13324 KB Output is correct
10 Correct 0 ms 13324 KB Output is correct
11 Correct 0 ms 13324 KB Output is correct
12 Correct 1 ms 13324 KB Output is correct
13 Correct 0 ms 13324 KB Output is correct
14 Correct 0 ms 13324 KB Output is correct
15 Correct 0 ms 13324 KB Output is correct
16 Correct 15 ms 13324 KB Output is correct
17 Correct 17 ms 13324 KB Output is correct
18 Correct 21 ms 13324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13324 KB Output is correct
2 Correct 0 ms 13324 KB Output is correct
3 Correct 0 ms 13324 KB Output is correct
4 Correct 0 ms 13324 KB Output is correct
5 Correct 0 ms 13324 KB Output is correct
6 Correct 0 ms 13324 KB Output is correct
7 Correct 0 ms 13324 KB Output is correct
8 Correct 0 ms 13324 KB Output is correct
9 Correct 0 ms 13324 KB Output is correct
10 Correct 1623 ms 16400 KB Output is correct
11 Correct 173 ms 13324 KB Output is correct
12 Correct 41 ms 13324 KB Output is correct
13 Correct 669 ms 14864 KB Output is correct
14 Correct 1085 ms 16400 KB Output is correct
15 Correct 0 ms 13324 KB Output is correct
16 Correct 0 ms 13324 KB Output is correct
17 Correct 0 ms 13324 KB Output is correct
18 Correct 0 ms 13324 KB Output is correct
19 Correct 0 ms 13324 KB Output is correct
20 Correct 0 ms 13324 KB Output is correct
21 Correct 11 ms 13324 KB Output is correct
22 Correct 2168 ms 16400 KB Output is correct
23 Correct 2176 ms 16400 KB Output is correct
24 Correct 1233 ms 16400 KB Output is correct
25 Correct 785 ms 14096 KB Output is correct
26 Correct 1642 ms 16400 KB Output is correct
27 Correct 856 ms 16400 KB Output is correct
28 Correct 1065 ms 16400 KB Output is correct
29 Correct 2121 ms 16400 KB Output is correct