Submission #1013173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013173		amirhoseinfar1385	로봇 (IOI13_robots)	C++17	76 / 100	3026 ms	37956 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){
    set<pair<int,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;j<(int)st.size()&&j<mid;j++){
                st.erase((*st.rbegin()));
            }
            l++;
        }
        st.insert(make_pair(allb[i].second,i));
    }
    while(l<(int)x.size()){
        for(int j=0;0<(int)st.size()&&j<mid;j++){
            st.erase((*st.rbegin()));
        }
        l++;
    }
    for(int j=0;j<(int)y.size();j++){
        for(int h=0;h<mid&&(int)st.size()>0&&(*st.begin()).first<=y[j];h++){
            st.erase(*st.begin());
        }
    }
//    cout<<"wtf: "<<mid<<endl;
  //  for(auto x:st){
    //    cout<<x.first<<" "<<x.second<<endl;
   // }
    if((int)st.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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10