Submission #566081

#	Time	Username	Problem	Language	Result	Execution time	Memory
566081		Leo121	Robots (IOI13_robots)	C++14	100 / 100	2016 ms	33856 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define for1(i, n) for(int i = 1; i <= int(n); ++ i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)

using namespace std;

struct ura {
    int w, s, idx;
};

struct ura2 {
    int pos, t;
    const bool operator < (const ura2 & a) const {
        return t < a.t;
    }
};

const int maxn = 1e6;
const int maxr = 5e4;
int robot1[maxr];
int robot2[maxr];
ura peso[maxn];
ura tamanio[maxn];
bool usados[maxn];
int n, m, t;
priority_queue<ura2> pq;

bool ordena1 (ura a, ura b){
    return a.w < b.w;
}

bool ordena2 (ura a, ura b) {
    return a.s < b.s;
}

void limpiar(){
    while(!pq.empty()){
        pq.pop();
    }
}

bool probar(int aux){
    memset(usados, 0, sizeof(usados));
    int cant = 0;
    int idx = 0;
    limpiar();
    for0(i, n){
        forn(j, idx, t - 1){
            if(peso[j].w < robot1[i]){
                pq.push({peso[j].idx, peso[j].s});
                idx ++;
                continue;
            }
            break;
        }
        cant += min((int) pq.size(), aux);
        int aux2 = (int) pq.size();
        for0(i, min(aux2, aux)){
            ura2 act = pq.top();
            usados[act.pos] = 1;
            pq.pop();
        }
    }
    limpiar();
    idx = 0;
    for0(i, m){
        forn(j, idx, t - 1){
            if(tamanio[j].s < robot2[i]){
                if(!usados[tamanio[j].idx]){
                    pq.push({tamanio[j].idx, tamanio[j].w});
                }
                idx ++;
                continue;
            }
            break;
        }
        cant += min((int) pq.size(), aux);
        int aux2 = (int) pq.size();
        for0(i, min(aux2, aux)){
            ura2 act = pq.top();
            usados[act.pos] = 1;
            pq.pop();
        }
    }
    return (cant == t);
}

int bs(){
    int li = 1, ls = t, mitad, res = -1;
    while(li <= ls){
        mitad = (li + ls) / 2;
        if(probar(mitad)){
            res = mitad;
            ls = mitad - 1;
        }
        else{
            li = mitad + 1;
        }
    }
    return res;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = A;
    m = B;
    for0(i, n){
        robot1[i] = X[i];
    }
    sort(robot1, robot1 + n);
    for0(i, m){
        robot2[i] = Y[i];
    }
    sort(robot2, robot2 + m);
    t = T;
    for0(i, t){
        peso[i] = {W[i], S[i], i};
        tamanio[i] = peso[i];
    }
    sort(peso, peso + t, ordena1);
    sort(tamanio, tamanio + t, ordena2);
    return bs();
}

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