Submission #1310268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310268		StefanSebez	Robots (IOI13_robots)	C++20	100 / 100	1231 ms	13116 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
vector<int>X,Y;
vector<pair<int,int>>Z;
bool Check(int mid){
    priority_queue<int>pq;
    for(int i=0,j=0;i<=X.size();i++){
        if(i==X.size()){
            while(j<Z.size())pq.push(Z[j++].se);
            break;
        }
        while(j<Z.size()&&Z[j].fi<X[i])pq.push(Z[j++].se);
        for(int k=0;k<mid;k++){
            if(pq.empty())break;
            pq.pop();
        }
    }
    for(int i=(int)Y.size()-1;i>=0;i--){
        for(int k=0;k<mid;k++){
            if(pq.empty())return true;
            if(pq.top()>=Y[i])return false;
            pq.pop();
        }
    }
    return pq.empty();
}
int putaway(int A, int B, int T, int X1[], int Y1[], int W[], int S[]) {
    for(int i=0;i<A;i++)X.pb(X1[i]);X.pb(0);
    sort(X.begin(),X.end());
    for(int i=0;i<B;i++)Y.pb(Y1[i]);Y.pb(0);
    sort(Y.begin(),Y.end());
    for(int i=0;i<T;i++)Z.pb({W[i],S[i]});
    sort(Z.begin(),Z.end());
    int l=1,r=Z.size(),res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(Check(mid))res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

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