Submission #1303795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303795		Mamikonm1	Robots (IOI13_robots)	C++17	100 / 100	1226 ms	12648 KiB

robots

#include "robots.h"
#include<bits//stdc++.h>
using namespace std;
#define V vector
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int l=1,r=T+1,md,it;
    sort(X,X+A);
    sort(Y,Y+B);
    reverse(Y,Y+B);
    V<pair<int,int>>rb;
    for(int i=0;i<T;++i)rb.push_back({W[i],S[i]});
    auto cmp=[&](pair<int,int>a,pair<int,int>b){
        if(a.first==b.first)return a.second>b.second;
        return a.first<b.first;
    };
    sort(begin(rb),end(rb),cmp);
    priority_queue<int>q;
    while(l<r){
        md=l+r>>1;
        it=0;
        while(!q.empty())q.pop();
        for(int i=0,j=0;i<A;++i,j=0){
            while(it<T and rb[it].first<X[i])q.push(rb[it++].second);
            while(!q.empty() and j<md)q.pop(),j++;
        }
        for(int i=it;i<T;++i)q.push(rb[i].second);
        for(int i=0,j=0;i<B;++i,j=0)
            while(j<md and !q.empty() and q.top()<Y[i])q.pop(),j++;
        if(q.empty())r=md;
        else l=md+1;
    }
    return r>T?-1:r;
}

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