Submission #566095

#	Time	Username	Problem	Language	Result	Execution time	Memory
566095		AlexRex0	Robots (IOI13_robots)	C++14	100 / 100	1763 ms	30032 KiB

robots

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

struct dato{
    int peso;
    int altura;
    int id;
};

bool compara(dato x, dato y){
    if(x.altura == y.altura){
        return x.peso < y.peso;
    }
    return x.altura < y.altura;
}

bool compara2(dato x, dato y){
    if(x.peso == y.peso){
        return x.altura < y.altura;
    }
    return x.peso < y.peso;
}

int color;
int visitado[1000002];
dato jugPeso[1000002];
dato jugAlt[1000002];
int roboA[50002];
int roboB[50002];


bool probar(int k, int n, int a, int b){
    bool ans = true;
    priority_queue<pair<int, int> > colaP;
    ///el primero es la altura, el segundo es el id
    priority_queue<pair<int, int> > colaP2;
    /// el primero es el peso, el segundo es el id
    int ind = 0;
    for(int i = 0; i < a; ++i){
        while(jugPeso[ind].peso < roboA[i] && ind < n){
            colaP.push({jugPeso[ind].altura, jugPeso[ind].id});
            ind++;
        }
        for(int j = 1; j <= k; ++j){
            if(!colaP.empty()){
                pair<int, int> sig;
                sig = colaP.top();
                colaP.pop();
                visitado[sig.second] = color;
            }else{
                break;
            }
        }
    }
    ind = 0;
    for(int i = 0; i < b; ++i){
        while(jugAlt[ind].altura < roboB[i] && ind < n){
            if(visitado[jugAlt[ind].id] != color){
                colaP2.push({jugAlt[ind].peso, jugAlt[ind].id});
            }
            ind++;
        }
        for(int j = 1; j <= k; ++j){
            if(!colaP2.empty()){
                pair<int, int> sig;
                sig = colaP2.top();
                colaP2.pop();
                visitado[sig.second] = color;
            }else{
                break;
            }
        }
    }
    for(int i = 0; i < n; ++i){
        if(visitado[i] != color) ans = false;
    }
    return ans;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int ans = -1, medio, sup = T, inf  = 1;
     for(int i = 0; i < T; ++i){
        dato aux;
        aux.id = i;
        aux.peso = W[i];
        aux.altura = S[i];
        jugPeso[i] = aux;
        jugAlt[i] = aux;
    }
    for(int i = 0; i < A; ++i){
        roboA[i] = X[i];
    }
    for(int i = 0; i < B; ++i){
        roboB[i] = Y[i];
    }
    sort(jugPeso, jugPeso + T, compara2);
    sort(jugAlt, jugAlt + T, compara);
    sort(roboA, roboA + A);
    sort(roboB, roboB + B);
    while(inf <= sup){
        medio = (inf + sup) / 2;
        color++;
        if(probar(medio, T, A, B)){
            ans = medio;
            sup = medio - 1;
        }else{
            inf = medio + 1;
        }
    }
    return ans;
}

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