Submission #599098

#	Time	Username	Problem	Language	Result	Execution time	Memory
599098		alirezasamimi100	Robots (IOI13_robots)	C++17	100 / 100	1585 ms	25124 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back
#define F first
#define S second

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A);
    sort(Y,Y+B);
    vector<pii> vec;
    for(int i=0; i<T; i++){
        vec.pb({W[i],S[i]});
        if(W[i]>=X[A-1] && S[i]>=Y[B-1]) return -1;
    }
    sort(vec.begin(),vec.end());
    int l=0,r=T;
    while(r-l>1){
        int m=(l+r)>>1,p=0;
        priority_queue<int> pq;
        for(int i=0; i<A; i++){
            while(p<T && vec[p].F<X[i]){
                pq.push(vec[p].S);
                p++;
            }
            int x=m;
            while(x && !pq.empty()){
                pq.pop();
                x--;
            }
        }
        vector<int> wtf;
        while(!pq.empty()){
            wtf.pb(pq.top());
            pq.pop();
        }
        while(p<T){
            wtf.pb(vec[p].S);
            p++;
        }
        p=0;
        sort(wtf.begin(),wtf.end());
        int k=wtf.size();
        for(int i=0; i<B; i++){
            int x=m;
            while(x && p<k && wtf[p]<Y[i]){
                x--;
                p++;
            }
        }
        if(p==k) r=m;
        else l=m;
    }
    return r;
}

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