Submission #82022

#	Time	Username	Problem	Language	Result	Execution time	Memory
82022		zoooma13	Robots (IOI13_robots)	C++14	90 / 100	1986 ms	66560 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX_T 1000006
#define MAX_A 50004
#define We first
#define Si second

int A ,B ,T;
int Weak[MAX_A];
int Small[MAX_A];
pair <int ,int> WeTs[MAX_T];

bool can(int X)
{
    int Weak_ptr = 0;
    priority_queue <int> pq;

    for(int i=0; i<A; i++)
    {
        while(Weak_ptr < T && WeTs[Weak_ptr].We < Weak[i])
            pq.push(WeTs[Weak_ptr++].Si);

        int CanHave = X;
        while(!pq.empty() && CanHave--)
            pq.pop();
    }

    while(Weak_ptr < T)
        pq.push(WeTs[Weak_ptr++].Si);

    for(int i=B-1; ~i; i--)
    {
        int CanHave = X;
        while(CanHave-- && !pq.empty() && pq.top() < Small[i])
            pq.pop();
    }

    return pq.empty();
}

int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {

    A = a ,B = b ,T = t;
    for(int i=0; i<A; i++)
        Weak[i] = X[i];
    for(int i=0; i<B; i++)
        Small[i] = Y[i];
    for(int i=0; i<T; i++)
        WeTs[i] = {W[i] ,S[i]};

    sort(Weak ,Weak+A);
    sort(Small ,Small+B);
    sort(WeTs ,WeTs+T);

    int st = 1 ,en = T ,mid;
    while(st <= en)
    {
        mid = (st+en)>>1;

        if(can(mid))
            en = mid-1;
        else
            st = mid+1;
    }

    return (en == T ? -1 : en+1);
}

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