oj.uz

Submission #963577

# Submission time Handle Problem Language Result Execution time Memory
963577 2024-04-15T11:09:39 Z simona1230 Robots (IOI13_robots) C++17
53 / 100
 785 ms 62792 KB 
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int a,b,t,x[50000],y[50000];
pair<long long,int> w[1000000],s[1000000];
long long wg[1000000],sz[1000000];
struct edge1
{
    long long w,s,id;
    edge1(){}
    edge1(long long _w,long long _s,long long i)
    {
        w=_w;
        s=_s;
        id=i;
    }
    bool operator<(const edge1&e)const
    {
        return e.s<s;
    }
};
priority_queue<edge1> q;
int used[1000000];

bool smart(int k)
{
    //cout<<k<<" * "<<endl;
    memset(used,0,sizeof(used));
    int id=0,in=0;
    for(int i=0;i<a;i++)
    {
        int cnt=0;
        while(id<t&&w[id].first<x[i])
        {
            int idx=w[id].second;
            q.push({wg[i],sz[i],idx});
            id++;
        }

        while(cnt<k&&q.size())
        {
            int t=q.top().id;
            //cout<<"/ "<<t<<endl;
            q.pop();
            cnt++;
            used[t]=1;
            in++;
        }
    }

    //cout<<"pout"<<endl;

    id=0;
    for(int i=0;i<b;i++)
    {
        int cnt=0;
        while(id<t&&s[id].first<y[i]&&cnt<k)
        {
            int idx=s[id].second;
            if(!used[idx])
            {
                cnt++;
                used[idx]=1;
                in++;
            }
            id++;
        }
    }
    /*for(int i=0;i<t;i++)
        cout<<used[i]<<" ";
    cout<<endl;*/
    while(q.size())q.pop();
    if(in==t)return 1;
    return 0;
}
// sort by s in pq, sort by w in va

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[])
{
    a=A;
    b=B;
    t=T;
    for(int i=0;i<a;i++)
        x[i]=X[i];
    for(int i=0;i<b;i++)
        y[i]=Y[i];
    for(int i=0;i<t;i++)
        w[i].first=W[i],s[i].first=S[i],w[i].second=s[i].second=i,wg[i]=W[i],sz[i]=S[i];

    sort(x,x+a);
    sort(y,y+b);
    sort(w,w+t);
    sort(s,s+t);

    int l=1,r=t;
    int ans=-1;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(smart(m))
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }

    return ans;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14796 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 710 ms 58504 KB Output is correct
5 Correct 785 ms 61880 KB Output is correct
6 Correct 40 ms 18332 KB Output is correct
7 Correct 510 ms 52700 KB Output is correct
8 Correct 739 ms 62792 KB Output is correct
9 Correct 768 ms 61372 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14788 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14680 KB Output is correct
8 Correct 2 ms 14788 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14680 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 2 ms 14804 KB Output is correct
16 Incorrect 13 ms 15340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14836 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14812 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14680 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 749 ms 62560 KB Output is correct
11 Correct 782 ms 60600 KB Output is correct
12 Correct 47 ms 18324 KB Output is correct
13 Correct 514 ms 53228 KB Output is correct
14 Correct 739 ms 61664 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14680 KB Output is correct
18 Correct 2 ms 14840 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 16 ms 15280 KB Output isn't correct
22 Halted 0 ms 0 KB -