Submission #964748

#	Time	Username	Problem	Language	Result	Execution time	Memory
964748		hirayuu_oj	Robots (IOI13_robots)	C++17	100 / 100	1447 ms	25544 KiB

robots

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10