Submission #748030

#	Time	Username	Problem	Language	Result	Execution time	Memory
748030		ETheBest3	Robots (IOI13_robots)	C++14	100 / 100	1634 ms	28728 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define lli int
using namespace std;
const lli MAXN=1000005, INF=999999999;
lli tree[4*MAXN], X[MAXN], Y[MAXN], S[MAXN], W[MAXN], A, B, T;
bool used[MAXN];
struct rob{
    lli w, s, ind;
    const bool operator <(rob p) const{
        if(w!=p.w)return w<p.w;
        return ind<p.ind;
    }
};
rob a[MAXN];
priority_queue<lli> pq;
bool check(lli br){
    lli p1=0;
    while(!pq.empty())pq.pop();
    for(lli i=0; i<A; i++){
        while(p1<T and a[p1].w<X[i]){
            pq.push(a[p1].s);
            p1++;
        }
        lli t=0;
        while(t<br){
            if(!pq.empty())pq.pop();
            else break;
            t++;
        }
    }
    while(p1<T){
        pq.push(a[p1].s);
        p1++;
    }
    for(lli i=B-1; i>=0; i--){
        lli t=0;
        while(t<br){
            if(!pq.empty() and pq.top()<Y[i])pq.pop();
            else break;
            t++;
        }
    }
    if(!pq.empty())return 0;
    return 1;
}
int bin_search(lli l, lli r){
    while(l<r-1){
        lli mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(check(l))return l;
    if(check(r))return r;
    return -1;
}
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
    A=A1;
    B=B1;
    T=T1;
    for(lli i=0; i<A; i++)X[i]=X1[i];
    for(lli i=0; i<B; i++)Y[i]=Y1[i];
    sort(X, X+A);
    sort(Y, Y+B);
    for(lli i=0; i<T; i++){
        W[i]=W1[i];
        S[i]=S1[i];
        a[i]={W[i], S[i], i};
    }
    sort(a, a+T);
    return bin_search(T/(A+B), T);
}

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