Submission #1013179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013179		amirhoseinfar1385	Robots (IOI13_robots)	C++17	100 / 100	1246 ms	28812 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=1000000+10;
vector<pair<int,int>>allb;
vector<int>x,y;
int n,m,t;
int dp[maxm],p;

bool check(int mid){
    priority_queue<int>st;
    int l=0;
    for(int i=0;i<(int)allb.size();i++){
        while(l<(int)x.size()&&x[l]<allb[i].first){
            for(int j=0;0<(int)st.size()&&j<mid;j++){
                st.pop();
            }
            l++;
        }
        st.push(allb[i].second);
    }
    while(l<(int)x.size()){
        for(int j=0;0<(int)st.size()&&j<mid;j++){
            st.pop();
        }
        l++;
    }
    vector<int>ham;
    while((int)st.size()>0){
        ham.push_back(st.top());
        st.pop();
    }
    for(int j=0;j<(int)y.size();j++){
        for(int h=0;h<mid&&(int)ham.size()>0&&(ham.back())<=y[j];h++){
           ham.pop_back();
        }
    }
    if((int)ham.size()==0){
        return 1;
    }
    return 0;
}

int solve(){
    int low=0,high=t+2,mid;
    while(high-low>1){
        mid=(high+low-1)>>1;
        if(check(mid)==0){
            low=mid+1;
        }else{
            high=mid+1;
        }
    }
    if(low>t){
        low=-1;
    }
    return low;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n=A;
    m=B;
    t=T;
    for(int i=0;i<n;i++){
        X[i]--;
        x.push_back(X[i]);
    }
    for(int i=0;i<m;i++){
        Y[i]--;
        y.push_back(Y[i]);
    }
    for(int i=0;i<t;i++){
        allb.push_back(make_pair(W[i],S[i]));
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    sort(allb.begin(),allb.end());
    return solve();
}

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