Submission #963978

#	Time	Username	Problem	Language	Result	Execution time	Memory
963978		irmuun	Robots (IOI13_robots)	C++17	100 / 100	1636 ms	28476 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]){
    pair<int,int>toy[T];
    for(int i=0;i<T;i++){
        toy[i].ff=W[i];
        toy[i].ss=S[i];
    }
    sort(toy,toy+T);
    sort(X,X+A);
    sort(Y,Y+B);
    int l=1,r=T+1;
    vector<bool>used(T);
    while(l<r){
        int mid=(l+r)/2;
        fill(all(used),0);
        priority_queue<pair<int,int>>pq;
        int le=0;
        for(int i=0;i<A;i++){
            while(le<T&&toy[le].ff<X[i]){
                pq.push({toy[le].ss,le});
                le++;
            }
            int cur=mid;
            while(cur--&&!pq.empty()){
                used[pq.top().ss]=true;
                pq.pop();
            }
        }
        while(!pq.empty()) pq.pop();
        for(int i=0;i<T;i++){
            if(!used[i]){
                pq.push({toy[i].ss,i});
            }
        }
        for(int i=B-1;i>=0;i--){
            int cur=mid;
            while(cur--&&!pq.empty()){
                if(pq.top().ff<Y[i]){
                    pq.pop();
                }
                else break;
            }
        }
        if(!pq.empty()) l=mid+1;
        else r=mid;
    }
    if(l==T+1) return -1;
    return l;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10