oj.uz

답안 #962815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962815 2024-04-14T08:36:01 Z simona1230 로봇 (IOI13_robots) C++17
90 / 100
 1707 ms 65536 KB 
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int a,b,t,x[50000],y[50000],w[1000000],s[1000000];

bool check(int k)
{
    int idx=t-1;
    for(int i=a-1;i>=0;i--)
    {
        int cnt=0;
        while(idx>=0&&cnt<k&&w[idx]<x[i])
        {
            idx--;
            cnt++;
        }
    }

    if(idx==-1)return 1;
    return 0;
}
vector<int> va[50000],vb[50000];

bool used[1000000];
bool smart(int k)
{
    for(int i=0;i<t;i++)
        used[i]=0;
    int in=0;
    for(int i=0;i<a;i++)
    {
        int cnt=0;
        for(int id=0;id<va[i].size();id++)
        {
            int j=va[i][id];
            if(!used[j])
            {
                used[j]=1;
                cnt++;
                in++;
            }
            if(cnt==k)break;
        }
    }

    for(int i=0;i<b;i++)
    {
        int cnt=0;
        for(int id=0;id<vb[i].size();id++)
        {
            int j=vb[i][id];
            if(!used[j])
            {
                used[j]=1;
                cnt++;
                in++;
            }
            if(cnt==k)break;
        }
    }
    if(in==t)return 1;
    return 0;
}

bool cmpa(int i,int j)
{
    return s[i]>s[j];
}
bool cmpb(int i,int j)
{
    return w[i]>w[j];
}

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]=W[i],s[i]=S[i];

    sort(x,x+a);
    sort(y,y+b);

    if(a+b==2&&t==2)
    {
        if(a==2)
        {
            sort(w,w+t);
            if(x[0]>w[0]&&x[1]>w[1])return 1;
            if(x[1]>w[1])return 2;
            return -1;
        }

        if(b==2)
        {
            sort(s,s+t);
            if(y[0]>s[0]&&y[1]>s[1])return 1;
            if(y[1]>s[1])return 2;
            return -1;
        }

        if(x[0]>w[0]&&y[0]>s[1]||x[0]>w[1]&&y[0]>s[0])return 1;
        if(x[0]<=w[0]&&y[0]<=s[0]||x[0]<=w[1]&&y[0]<=s[1])return -1;
        return 2;
    }

    if(b==0)
    {
        sort(w,w+t);
        int l=1,r=t;
        int ans=-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            if(check(m))
            {
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }

        return ans;
    }

    for(int i=0;i<a;i++)
    {
        for(int j=0;j<t;j++)
        {
            if(x[i]>w[j])va[i].push_back(j);
        }
        sort(va[i].begin(),va[i].end(),cmpa);
    }

    for(int i=0;i<b;i++)
    {
        for(int j=0;j<t;j++)
        {
            if(y[i]>s[j])vb[i].push_back(j);
        }
        sort(vb[i].begin(),vb[i].end(),cmpb);
    }

    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;
}

Compilation message

robots.cpp: In function 'bool smart(int)':
robots.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int id=0;id<va[i].size();id++)
      |                      ~~^~~~~~~~~~~~~
robots.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int id=0;id<vb[i].size();id++)
      |                      ~~^~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:107:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  107 |         if(x[0]>w[0]&&y[0]>s[1]||x[0]>w[1]&&y[0]>s[0])return 1;
      |            ~~~~~~~~~^~~~~~~~~~~
robots.cpp:108:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  108 |         if(x[0]<=w[0]&&y[0]<=s[0]||x[0]<=w[1]&&y[0]<=s[1])return -1;
      |            ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 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 2 ms 10588 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 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 144 ms 20968 KB Output is correct
5 Correct 136 ms 20648 KB Output is correct
6 Correct 21 ms 11704 KB Output is correct
7 Correct 131 ms 19796 KB Output is correct
8 Correct 160 ms 21032 KB Output is correct
9 Correct 141 ms 20780 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 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 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10712 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10708 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 495 ms 33496 KB Output is correct
17 Correct 504 ms 34224 KB Output is correct
18 Correct 928 ms 54180 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10688 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 138 ms 23592 KB Output is correct
11 Correct 130 ms 23296 KB Output is correct
12 Correct 21 ms 12120 KB Output is correct
13 Correct 137 ms 21976 KB Output is correct
14 Correct 145 ms 23516 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 509 ms 33552 KB Output is correct
22 Runtime error 1707 ms 65536 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -