Submission #497286

#	Time	Username	Problem	Language	Result	Execution time	Memory
497286		Ozy	Parrots (IOI11_parrots)	C++17	99 / 100	6 ms	1316 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <iostream>
#include <vector>

using namespace std;

#define lli long long
#define MAXN 22

lli dp[MAXN][MAXN];

void llena_tabla(){

    // Voy a llenar la tabla dinámica de caminos desde el final (16, 20) hacia el inicio (0,0).
    // es una tabla dinámica normal en que te puedes mover a la izquierda y abajo en este caso.
    // La inicialización es que la fila de arriba y la columna de la derecha sólo tienen un camino.
    for(int fil = 0; fil <= 16; ++fil) dp[fil][20] = 1;
    for(int col = 0; col <= 20; ++col) dp[16][col] = 1;

    // Luego hay que llenar la tabla
    // Los lugares van de 0 a 20 porque voy a dividir en grupos de 4 números entonces puedo enviar 20 pericos por cada grupo.
    for(int col = 19; col >= 0; --col){
        // Las filas representan los valores, van del 0 al 16 porque el 0 significa que no esta y luego son los valores de 0 a 15
        // uso solo valores de 0 a 15 porque voy a usar 4 bits para indicar el grupo al que pertenece el número y
        // 4 bits para el valor en sí, entonces sólo podré poner valores de 0 a 15.
        for(int fil = 15; fil >= 0; --fil){
            dp[fil][col] = dp[fil + 1][col] + dp[fil][col + 1];
        }
    }
}

vector<int> construye_secuencia(lli grupo, lli cuatroNumeros){
    int valor = 0; // Esta variable lleva el número de la secuencia.
    int fil = 0, col = 0; // Llevan la posición en la tabla dinámica.
    vector<int> res;

    // Para construir la secuencia será necesario fijarse en la tabla de caminos.
    // Si moviéndose a la derecha hay suficientes caminos para llegar al número que se requiere,
    // entonces hay que moverse a la derecha.  En caso contrario hay que moverse hacia arriba (avanzando un valor)
    // y tomando en cuenta todas las opciones que se hubieran usado si se movia a la derecha.
    while (fil < 16 || col < 20){
        if (dp[fil][col + 1] >= cuatroNumeros){ // Hay suficientes opciones sin avanzar de numero
            col++;
            if (fil) res.push_back((grupo << 4) + fil - 1);
        }
        else{ // No hay suficientes caminos avanzando a la derecha, hay que aumentar de número
            cuatroNumeros -= dp[fil][col + 1];
            fil++;
        }
    }
    return res;
}

void encode(int N, int M[])
{
    // Construye la tabla de caminos
    llena_tabla();

    // Haz grupos de 4 números
    lli cuatroNumeros;
    lli grupo = 0, pos = 0;
    while (pos < N){
        cuatroNumeros = 0;
        for(int i = 0; i <= 3; ++i){
            cuatroNumeros <<= 8; // recorrelo 8 lugares para hacer lugar al nuevo
            if (pos < N) cuatroNumeros += M[pos++]; // agregale el nuevo número e incrementa la posición.
        }

        // construye la secuencia y enviala
        vector<int> secuencia = construye_secuencia(grupo, cuatroNumeros + 1);

        for(auto s : secuencia) send(s);

        ++grupo; // avanza al siguiente grupo.
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define lli long long
#define MAXN 22

lli dp_dec[MAXN][MAXN];

void llena_tabla_dec(){
    for(int fil = 0; fil <= 16; ++fil) dp_dec[fil][20] = 1;
    for(int col = 0; col <= 20; ++col) dp_dec[16][col] = 1;

    for(int col = 19; col >= 0; --col)
        for(int fil = 15; fil >= 0; --fil)
            dp_dec[fil][col] = dp_dec[fil + 1][col] + dp_dec[fil][col + 1];
}

lli construye_numero(vector<int> &secuencia){
    int fil = 0, col = 0; // Llevan la posición en la tabla dinámica.
    lli res = 0;

    // Primero hay que normalizar la secuencia. Hay que sumarle 1 a cada número para
    // que estén en el rango [1, 16] y agregarle 0's si le faltan posiciones.
    for(int i = 0; i < secuencia.size(); ++i) secuencia[i]++;
    while (secuencia.size() < 20) secuencia.push_back(0);

    // Después hay que ordenar la secuencia
    sort(secuencia.begin(), secuencia.end());

    // Finalmente, para reconstruir el número a partir de la secuencia de nuevo se usa
    // la tabla dinámica pero esta vez sumando los caminos que se van dejando sin usar.
    lli valorprev = 0; // Esta variable es para saber si cambia el valor.
    for(int i = 0; i < 20; ++i){
        if (secuencia[i] != valorprev){
            while (fil < secuencia[i]) {
                res += dp_dec[fil][col + 1];
                ++fil;
            }
            valorprev = secuencia[i];
        }
        ++col;
    }

    return res;
}

void decode(int N, int L, int X[])
{
    llena_tabla_dec();

    vector<int> mensaje;
    vector<vector<int> > secuencia(16);
    lli grupo, valor, pos;

    // Para cada perico del mensaje obten el valor y el grupo al que pertenece.
    // Agrega el valor a la secuencia de ese grupo para luego ordenar y reconstruir.
    for(int i = 0; i < L; ++i){
        grupo = X[i] >> 4;
        valor = X[i] & 15;
        secuencia[grupo].push_back(valor);
    }

    // Decodifica cada secuencia para generar los números
    lli cuatroNumeros;
    pos = 0;
    for(int i = 0; i < 16; ++i){
        cuatroNumeros = construye_numero(secuencia[i]);
        for(int j = 0; j <= 3; ++j) if (pos < N){
            mensaje.push_back((cuatroNumeros & 0xFF000000) >> 24); // Escribe el último número
            cuatroNumeros <<= 8; // recorre el numero para el siguiente byte.
            ++pos;
        }
        if (pos >= N) break;
    }

    for(auto n : mensaje) output(n);
}

Compilation message (stderr)

encoder.cpp: In function 'std::vector<int> construye_secuencia(long long int, long long int)':
encoder.cpp:34:9: warning: unused variable 'valor' [-Wunused-variable]
   34 |     int valor = 0; // Esta variable lleva el número de la secuencia.
      |         ^~~~~

decoder.cpp: In function 'long long int construye_numero(std::vector<int>&)':
decoder.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < secuencia.size(); ++i) secuencia[i]++;
      |                    ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 18 / 19