Submission #883498

#	Time	Username	Problem	Language	Result	Execution time	Memory
883498		JakobZorz	Robots (IOI13_robots)	C++14	100 / 100	1321 ms	26948 KiB

robots

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

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

bool check(int k){
    priority_queue<int>ms;
    int in=0;
    for(int ia=0;ia<a;ia++){
        while(in<n&&t[in].first<xa[ia]){
            ms.push(t[in].second);
            in++;
        }
        
        for(int i=0;i<k&&!ms.empty();i++){
            ms.pop();
        }
    }
    
    while(in<n){
        ms.push(t[in].second);
        in++;
    }
    
    for(int ib=0;ib<b&&!ms.empty();ib++){
        for(int i=0;i<k&&!ms.empty();i++){
            if(ms.top()>=xb[ib])
                return false;
            ms.pop();
        }
    }
    
    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<b;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);
    reverse(xb,xb+b);
    sort(t,t+n);
    
    if((a==0||t[n-1].first>=xa[a-1])&&(b==0||t[n-1].second>=xb[0]))
        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: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10