Submission #883488

#	Time	Username	Problem	Language	Result	Execution time	Memory
883488		JakobZorz	Robots (IOI13_robots)	C++14	0 / 100	3007 ms	44756 KiB

robots

#include"robots.h"
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int n,a,b;
int xa[50000];
int xb[50000];
pair<int,int>t[1000000];

bool check(int k){
    multiset<int>ms;
    int in=0;
    for(int ia=0;ia<a;ia++){
        while(in<n&&t[in].first<xa[ia]){
            ms.insert(t[in].second);
            in++;
        }
        
        for(int i=0;i<k&&!ms.empty();i++){
            ms.erase(--ms.end());
        }
    }
    
    while(in<n){
        ms.insert(t[in].second);
        in++;
    }
    
    for(int ib=b-1;ib>=0&&!ms.empty();ib--){
        for(int i=0;i<k&&!ms.empty();i++){
            if(*--ms.end()>=xb[ib])
                return false;
            ms.erase(--ms.end());
        }
    }
    
    return ms.empty();
}

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]) {
    n=T;
    a=A;
    b=B;
    for(int i=0;i<a;i++)
        xa[i]=X[i];
    for(int i=0;i<a;i++)
        xb[i]=Y[i];
    for(int i=0;i<n;i++){
        t[i]={W[i],S[i]};
    }
    
    sort(xa,xa+a);
    sort(xb,xb+b);
    sort(t,t+n);
    
    if(t[n-1].first>=xa[a-1]&&t[n-1].second>=xb[b-1])
        return -1;
    
    int l=0,r=n;
    while(l<r-1){
        int m=(l+r)/2;
        if(check(m))
            r=m;
        else
            l=m;
    }
    
    return r;
}

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