oj.uz

답안 #964748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964748 2024-04-17T13:26:56 Z hirayuu_oj 로봇 (IOI13_robots) C++17
100 / 100
 1447 ms 25544 KB 
#include "robots.h"
#include<bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<int> x(A);
    rep(i,A){
        x[i]=X[i];
    }
    sort(all(x));
    vector<int> y(B);
    rep(i,B){
        y[i]=Y[i];
    }
    sort(all(y));
    vector<pair<int,int>> toy(T);
    rep(i,T){
        toy[i]={W[i],S[i]};
    }
    sort(all(toy));
    int ng=0,ok=T+1;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        int cnt=0;
        priority_queue<int,vector<int>,less<int>> pq1; 
        rep(i,A){
            while(cnt<T&&toy[cnt].first<x[i]){
                pq1.push(toy[cnt].second);
                cnt++;
            }
            rep(j,mid){
                if(pq1.empty())break;
                pq1.pop();
            }
        }
        priority_queue<int,vector<int>,greater<int>> pq2;
        while(cnt<T){
            pq2.push(toy[cnt].second);
            cnt++;
        }
        while(!pq1.empty()){
            pq2.push(pq1.top());
            pq1.pop();
        }
        rep(i,B){
            rep(j,mid){
                if(pq2.empty())break;
                if(pq2.top()>=y[i])break;
                pq2.pop();
            }
        }
        if(pq2.empty())ok=mid;
        else ng=mid;
    }
    if(ok==T+1)return -1;
    return ok;
}

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 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 4440 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1012 ms 12380 KB Output is correct
5 Correct 1408 ms 12920 KB Output is correct
6 Correct 22 ms 5208 KB Output is correct
7 Correct 317 ms 10752 KB Output is correct
8 Correct 701 ms 13204 KB Output is correct
9 Correct 1369 ms 13028 KB Output is correct

Subtask #3
25.0 / 25.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 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 4540 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 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4540 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 4444 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 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4596 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 12 ms 4956 KB Output is correct
17 Correct 12 ms 4916 KB Output is correct
18 Correct 16 ms 4956 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 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 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 998 ms 12600 KB Output is correct
11 Correct 1403 ms 12948 KB Output is correct
12 Correct 22 ms 5208 KB Output is correct
13 Correct 294 ms 10972 KB Output is correct
14 Correct 727 ms 12084 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4540 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 11 ms 4956 KB Output is correct
22 Correct 1354 ms 23764 KB Output is correct
23 Correct 1398 ms 23324 KB Output is correct
24 Correct 380 ms 24704 KB Output is correct
25 Correct 350 ms 21444 KB Output is correct
26 Correct 416 ms 24824 KB Output is correct
27 Correct 612 ms 24668 KB Output is correct
28 Correct 727 ms 24608 KB Output is correct
29 Correct 1447 ms 25544 KB Output is correct