Submission #990457

#	Time	Username	Problem	Language	Result	Execution time	Memory
990457		aaaaaarroz	Robots (IOI13_robots)	C++17	100 / 100	1305 ms	25484 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