Submission #82025

#	Time	Username	Problem	Language	Result	Execution time	Memory
82025		zoooma13	Robots (IOI13_robots)	C++14	100 / 100	2059 ms	19224 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: 10 / 10