oj.uz

Submission #964747

# Submission time Handle Problem Language Result Execution time Memory
964747 2024-04-17T13:24:46 Z hirayuu_oj Robots (IOI13_robots) C++17
28 / 100
 1388 ms 23388 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];
    }
    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

# Verdict Execution time Memory 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 4536 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory 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 1068 ms 17896 KB Output is correct
5 Correct 1388 ms 23388 KB Output is correct
6 Correct 25 ms 6332 KB Output is correct
7 Correct 305 ms 19372 KB Output is correct
8 Correct 702 ms 22860 KB Output is correct
9 Correct 1383 ms 23328 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4696 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 4536 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 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 4444 KB Output is correct
12 Incorrect 1 ms 4440 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4448 KB Output is correct
4 Correct 1 ms 4544 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4524 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Incorrect 1 ms 4440 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 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 4696 KB Output is correct
5 Correct 1 ms 4444 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 4544 KB Output is correct
10 Correct 999 ms 17944 KB Output is correct
11 Correct 1349 ms 23316 KB Output is correct
12 Correct 22 ms 6224 KB Output is correct
13 Correct 288 ms 19208 KB Output is correct
14 Correct 697 ms 22828 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Halted 0 ms 0 KB -