oj.uz

답안 #963588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963588 2024-04-15T11:17:43 Z simona1230 로봇 (IOI13_robots) C++17
100 / 100
 1730 ms 38624 KB 
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int a,b,t,x[50000],y[50000];
pair<int,int> w[1000000],s[1000000];
int wg[1000000],sz[1000000];
struct edge
{
    int w,s,id;
    edge(){}
    edge(int _w,int _s,int i)
    {
        w=_w;
        s=_s;
        id=i;
    }
    bool operator<(const edge&e)const
    {
        return e.s>s;
    }
};
priority_queue<edge> 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[idx],sz[idx],idx});
            id++;
        }
        //cout<<i<<"-"<<endl;

        while(cnt<k&&q.size())
        {
            int t=q.top().id;
            //cout<<"/ "<<t<<" "<<wg[t]<<" "<<sz[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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10584 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10452 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 1397 ms 26820 KB Output is correct
5 Correct 1724 ms 26664 KB Output is correct
6 Correct 34 ms 8020 KB Output is correct
7 Correct 623 ms 23776 KB Output is correct
8 Correct 961 ms 26844 KB Output is correct
9 Correct 1695 ms 26688 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 4440 KB Output is correct
13 Correct 2 ms 6488 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 2 ms 6612 KB Output is correct
14 Correct 3 ms 6492 KB Output is correct
15 Correct 2 ms 6488 KB Output is correct
16 Correct 15 ms 7044 KB Output is correct
17 Correct 16 ms 7260 KB Output is correct
18 Correct 20 ms 7256 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1404 ms 26880 KB Output is correct
11 Correct 1713 ms 26816 KB Output is correct
12 Correct 31 ms 8032 KB Output is correct
13 Correct 702 ms 23616 KB Output is correct
14 Correct 977 ms 26836 KB Output is correct
15 Correct 5 ms 6488 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 3 ms 6492 KB Output is correct
20 Correct 2 ms 6488 KB Output is correct
21 Correct 13 ms 6900 KB Output is correct
22 Correct 200 ms 30984 KB Output is correct
23 Correct 1703 ms 37312 KB Output is correct
24 Correct 656 ms 38624 KB Output is correct
25 Correct 544 ms 33752 KB Output is correct
26 Correct 141 ms 32400 KB Output is correct
27 Correct 849 ms 38260 KB Output is correct
28 Correct 990 ms 38204 KB Output is correct
29 Correct 1730 ms 38528 KB Output is correct