Submission #1013155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013155		amirhoseinfar1385	Robots (IOI13_robots)	C++17	14 / 100	3091 ms	12836 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){
    for(int i=1;i<=t;i++){
        dp[i]=0;
    }
    dp[0]=1;
    int cnt=1;
    for(int i=0;i<(int)allb.size();i++){
        int p=lower_bound(y.begin(),y.end(),allb[i].second)-y.begin();
        int ps=((int)y.size()-p)*mid;
        ps=min(ps,cnt);
        p=lower_bound(x.begin(),x.end(),allb[i].first)-x.begin();
        int suf=(cnt)-((int)x.size()-p)*mid;
        suf=max(suf,0);
        for(int j=cnt;j>=0;j--){
            if(j>=suf&&dp[j]==1){
                continue;
            }
            if(j<=ps&&j!=0&&dp[j-1]==1){
                dp[j]=1;
                continue;
            }
            dp[j]=0;
        }
        cnt++;
    }
    for(int i=0;i<=t;i++){
        if(dp[i]){
   //         cout<<"ha: "<<i<<endl;
            return 1;
        }
    }
 //   cout<<"nago"<<endl;
    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: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10