제출 #1298408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298408		gesp3011v2	앵무새 (IOI11_parrots)	C++20	100 / 100	11 ms	936 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
short m[64];
ll sm[16];
//combinaciones
ll C(int n, int r){
    ll ret=1,dw=1;
    for(ll i=2;i<=r;i++) dw*=i;
    for(ll i=n-r+1;i<=n;i++){
        ll g=gcd(i,dw);
        dw/=g;
        ret*=i/g;
    }
    return ret;
}
short multi[21],mid=0;
//encodear con combinaciones
void enc(int len, short ele, ll rnk){
    //ele:elemento
    if(len==0) return;
    //busco el elemento mas pequeño posible
    while(rnk>=C(15-ele+len-1,15-ele)){
        rnk-=C(15-ele+len-1,15-ele);
        ele++;
    }
    multi[mid++]=ele;//guarda el elemento
    enc(len-1,ele,rnk);//proceso lo demas
}
//SD:send data
void SD(int prf,ll msg){
    int len=0;
    //determino cuantos mensaje necesito
    while(msg>=C(16+len,16)) len++;
    if(len==0) return;
    msg-=C(15+len,16);//ajusto el idx
    mid=0;
    enc(len,0,msg);//convierto el numero a combinacion
    //envio cada elemento con prefijo
    for(int i=0;i<len;i++) send(prf|multi[i]);
}
void encode(int N, int M[]){
    for(int i=0;i<N;i++) m[i]=M[i];
    //divido los datos en grupos de 4 bytes(32 bits)
    for(int id=0;id*4<N;id++){
        int st=id*4;
        sm[id]=0;
        //combino 4 numeros de 8 bits en 32 bits
        for(int j=st+3;j>=st;j--) sm[id]=(sm[id]<<8)|m[j];
        SD(id<<4,sm[id]);
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

short M[64];
vector<int>ele[16];
ll SM[16];

ll c(int n, int r){
    ll ret=1,dw=1;
    for(ll i=2;i<=r;i++) dw*=i;
    for(ll i=n-r+1;i<=n;i++){
        ll g=gcd(i,dw);
        dw/=g;
        ret*=i/g;
    }
    return ret;
}
//decodificacion combinatoria1
void DC(int id){
    SM[id]=0;
    if(ele[id].empty()) return;
    int len=ele[id].size();
    SM[id]=c(15+len,16);
    sort(ele[id].begin(),ele[id].end());
    int prf=0;
    for(int cur:ele[id]){
        len--;
        while(prf<cur){
            SM[id]+=c(15-prf+len,15-prf);
            prf++;
        }
    }
    return;
}

//mensage : [PPP VVV]
// PPP:prefijo, VVV:valor
//cada mensaje tiene 4 bits superiores e inferiores,
//superiores:ID del grupo
//inferiores:valor del elemento de la combinacion

void decode(int N, int L, int X[]){
    for(int i=0;i<16;i++) ele[i].clear();
    for(int i=0;i<L;i++) ele[X[i]>>4].push_back(X[i]&15);//agrupo por prefijo
    for(int id=0;id<16;id++){
        DC(id);
        //extraccion de los 4 numeros orginales1
        for(int i=(id<<2);i<=((id<<2)|3);i++){
            M[i]=(SM[id]&255);//extraer byte por byte
            SM[id]>>=8;
        }
    }
    for(int i=0;i<N;i++)output(M[i]);
}

//combinatorio que uso , combinaciones con repeticion
//C(n+r-1,r)

/**
EJ
num:1000
encoder:
supongamos que los comvierte a [3,7]
enviamos dos mensajes:(pref|3) y (pref|7)
nota:con OR concateno
decoder:
recibe [3,7]
los ordena(ya estan ordenados de menor a mayor)
recontruye el numero:C(15+2,16)+C(15-0+1,15-0)+...
con esto se obtiene 1000 de nuevo
**/

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