Submission #757293

#	Time	Username	Problem	Language	Result	Execution time	Memory
757293		safaricola	Robots (IOI13_robots)	C++17	100 / 100	1688 ms	32328 KiB

robots

#include<bits/stdc++.h>
using namespace std;
#include "robots.h"
#define rep(i,n) for(int i=0; i<n; i++)
#define ii pair<int,int>
#define f first
#define s second
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    ii r[1000010];
    rep(i,T)r[i]={W[i],S[i]};
    sort(r,r+T);
    sort(X,X+A);
    sort(Y,Y+B);
    int s=0, e=T+1, m;
    while(e-s>1){
        m=(e+s)/2;
        //cout<<m<<' ';
        priority_queue<ii> pq;
        int ind=0;
        rep(i,A){
            while(ind<T&&r[ind].f<X[i]){
                pq.push({r[ind].s,r[ind].f});
                ind++;
            }
            int M=m;
            while(M--&&pq.size()){
                pq.pop();
            }
        }
        while(ind<T)pq.push({r[ind].s,r[ind].f}),ind++;
        //cout<<pq.size();
        for(int i=B-1; i>=0; i--){
            int M=m;
            if(pq.size()&&pq.top().f>=Y[i])break;
            while(M--&&pq.size()){
                pq.pop();
            }
        }
        //cout<<endl;
        if(pq.empty())e=m;
        else s=m;
    }
    return ( e==T+1 ? -1 : e);
}

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