oj.uz

답안 #101373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101373 2019-03-18T19:06:38 Z MohamedAhmed0 로봇 (IOI13_robots) C++14
100 / 100
 1908 ms 13628 KB 
#include "robots.h"
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 50005 ;

int n , m ;

int Weight[MAX] , Size[MAX] ;

vector< vector<int> >appear ;

//the check function that return true if robots can put away toys in mid second and otherwise it will return false
bool check(int mid)
{
    priority_queue<int>q ;
    //put away toys using weak robots.
    for(int i = 0 ; i < n ; ++i)
    {
        for(int j = 0 ; j < appear[i].size() ; ++j)
            q.push(appear[i][j]) ;
        int sz = q.size() ;
        for(int j = 0 ; j < min(sz , mid) ; ++j)
            q.pop() ;
    }
    //handle case for toys that their weight is more than all weak robots weight.
    for(int j = 0 ; j < appear[n].size() ; ++j)
        q.push(appear[n][j]) ;
    //put away remaining toys using small robots.
    for(int i = 0 ; i < m ; ++i)
    {
        int sz = q.size() ;
        for(int j = 0 ; j < min(sz , mid) ; ++j)
        {
            int a = q.top() ;
            if(a >= Size[i])
                break;
            q.pop() ;
        }
    }
    if(q.empty())
        return 1 ;
    return 0 ;
}

int putaway(int A , int B , int T , int X[] , int Y[] , int W[] , int S[])
{
    for(int i = 0 ; i < A ; ++i)
        Weight[i] = X[i] ;
    for(int i = 0 ; i < B ; ++i)
        Size[i] = Y[i] ;
    sort(Weight , Weight + A) ;
    sort(Size , Size + B) ;
    n = A , m = B ;
    appear.resize(A+1) ;
    for(int i = 0 ; i < T ; ++i)
    {
        int idx1 = upper_bound(Weight , Weight + A , W[i]) - Weight ;
        int idx2 = upper_bound(Size , Size + B , S[i]) - Size ;
        //if current toy weight is bigger than weight of all weak robots and its size is more than size of all small robots
        if(idx1 == A && idx2 == B)
            return -1 ;
        appear[idx1].push_back(S[i]) ;
    }
    reverse(Size , Size + B) ;
    //make binary search
    int l = 1 , r = T , ans;
    while(l <= r)
    {
        int mid = (l + r) / 2 ;
        if(check(mid))
            r = mid-1 , ans = mid;
        else
            l = mid+1 ;
    }
    return ans ;
}

Compilation message

robots.cpp: In function 'bool check(int)':
robots.cpp:21:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < appear[i].size() ; ++j)
                         ~~^~~~~~~~~~~~~~~~~~
robots.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0 ; j < appear[n].size() ; ++j)
                     ~~^~~~~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:68:25: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int l = 1 , r = T , ans;
                         ^~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1469 ms 12688 KB Output is correct
5 Correct 177 ms 8192 KB Output is correct
6 Correct 54 ms 3960 KB Output is correct
7 Correct 653 ms 11632 KB Output is correct
8 Correct 922 ms 12688 KB Output is correct
9 Correct 1761 ms 12188 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 412 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 21 ms 768 KB Output is correct
17 Correct 20 ms 640 KB Output is correct
18 Correct 22 ms 640 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1410 ms 12912 KB Output is correct
11 Correct 185 ms 8092 KB Output is correct
12 Correct 52 ms 4016 KB Output is correct
13 Correct 666 ms 11812 KB Output is correct
14 Correct 925 ms 12752 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 14 ms 708 KB Output is correct
22 Correct 1659 ms 11040 KB Output is correct
23 Correct 1720 ms 12072 KB Output is correct
24 Correct 662 ms 13076 KB Output is correct
25 Correct 739 ms 11136 KB Output is correct
26 Correct 745 ms 12472 KB Output is correct
27 Correct 913 ms 13628 KB Output is correct
28 Correct 1004 ms 13080 KB Output is correct
29 Correct 1908 ms 12692 KB Output is correct