oj.uz

답안 #982592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982592 2024-05-14T13:04:28 Z kwongweng 로봇 (IOI13_robots) C++17
100 / 100
 2982 ms 35728 KB 
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

/*
Solution is binary search
*/

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A); sort(Y,Y+B);
    FOR(i,0,T){
        if (W[i]>=X[A-1] && S[i]>=Y[B-1]) return -1;
    }
    int l = 0, r = T+1;
    vii w(T+A);
    FOR(i,0,T) w[i] = {W[i],S[i]};
    FOR(i,T,T+A) w[i] = {X[i-T],0};
    sort(w.begin(), w.end());
    while (r-l>1){
        int mid = (l+r)/2;
        priority_queue<int> p;
        FOR(i,0,T+A){
            if (w[i].se > 0){
                p.push(w[i].se); continue;
            }
            int cnt = 0;
            while (!p.empty() && cnt < mid){
                p.pop(); cnt++;
            }
        }
        vii rem;
        while (!p.empty()){
            rem.pb({p.top(),1});
            p.pop();
        }
        FOR(i,0,B) rem.pb({Y[i],0});
        sort(rem.begin(), rem.end());
        priority_queue<int> q;
        FOR(i,0,rem.size()){
            if (rem[i].se>0){
                q.push(rem[i].fi); continue;
            }
            int cnt = 0;
            while (!q.empty() && cnt < mid){
                q.pop(); cnt++;
            }
        }
        if (q.empty()){
            r=mid;
        }else{
            l=mid;
        }
    }
    return r;
}

Compilation message

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:10:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   51 |         FOR(i,0,rem.size()){
      |             ~~~~~~~~~~~~~~             
robots.cpp:51:9: note: in expansion of macro 'FOR'
   51 |         FOR(i,0,rem.size()){
      |         ^~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1000 ms 23672 KB Output is correct
5 Correct 99 ms 15184 KB Output is correct
6 Correct 29 ms 6492 KB Output is correct
7 Correct 297 ms 20812 KB Output is correct
8 Correct 720 ms 25048 KB Output is correct
9 Correct 1335 ms 25816 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 11 ms 4916 KB Output is correct
17 Correct 13 ms 4956 KB Output is correct
18 Correct 18 ms 4952 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 992 ms 23592 KB Output is correct
11 Correct 96 ms 15120 KB Output is correct
12 Correct 25 ms 6488 KB Output is correct
13 Correct 294 ms 20812 KB Output is correct
14 Correct 737 ms 24988 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 12 ms 4956 KB Output is correct
22 Correct 2982 ms 34496 KB Output is correct
23 Correct 1337 ms 24496 KB Output is correct
24 Correct 402 ms 25024 KB Output is correct
25 Correct 456 ms 22728 KB Output is correct
26 Correct 983 ms 35728 KB Output is correct
27 Correct 762 ms 29688 KB Output is correct
28 Correct 865 ms 28692 KB Output is correct
29 Correct 1535 ms 30604 KB Output is correct