Submission #549960

#	Time	Username	Problem	Language	Result	Execution time	Memory
549960		CyberSleeper	Robots (IOI13_robots)	C++14	100 / 100	322 ms	20968 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    int banyak[A+1], ans=-1, tmp, banyak2[B+1];
    long long simp;
    memset(banyak, 0, sizeof(banyak)); memset(banyak2, 0, sizeof(banyak2));
    sort(X, X+A); sort(Y, Y+B);
    vector< pair<int, int> > lokasi;
    for(int i=0; i<T; i++){
        W[i]=upper_bound(X, X+A, W[i])-X;
        S[i]=upper_bound(Y, Y+B, S[i])-Y;
        banyak[W[i]]++;
        lokasi.push_back(mp(W[i], S[i]));
        if(W[i]==A && S[i]==B)
            return ans;
    }
    sort(lokasi.begin(), lokasi.end());
    for(int i=1; i<=A; i++)
        banyak[i]+=banyak[i-1];
    int L=1, R=T, M;
    while(L<=R){
        M=(L+R)/2;
        memset(banyak2, 0, sizeof(banyak2));
        if(A)
            tmp=banyak[A-1];
        else
            tmp=0;
        for(int i=tmp; i<T; i++)
            banyak2[lokasi[i].se]++;
        simp=0;
        for(int i=A-1; i>=0; i--){
            if(i>0){
                tmp=banyak[i]-banyak[i-1];
            }else{
                tmp=banyak[i];
            }
            //cout << M << ' ' << tmp << ' ' << simp << endl;
            if(tmp>M){
                if(simp>(tmp-M)){
                    simp-=tmp-M;
                    tmp=M;
                }else{
                    tmp-=simp;
                    simp=0;
                }
            }
            //cout << i << ' ' << L << ' ' << M << ' ' << R << endl;
            if(tmp>M){
                for(int j=0; j<tmp-M; j++){
                    if(i==0)
                        banyak2[lokasi[j].se]++;
                    else
                        banyak2[lokasi[banyak[i-1]+j].se]++;
                }
            }else{
                simp+=M-tmp;
            }
        }
        simp=0;
        //cout << "B " << banyak2[1] << endl;
        for(int i=B-1; i>=0; i--){
            //cout << banyak2[i] << ' ' << M << endl;
            simp+=M-banyak2[i];

            if(simp<0)
                break;
        }
        if(banyak2[B]){
            simp=-1;

        }
        //cout << M << endl << ans << ' ' << simp << "}\n";
        if(simp<0){
            L=M+1;
        }else{
            ans=M;
            R=M-1;
        }
    }
    //cout << "good\n";
    return ans;
}

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