Submission #1270640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270640		AlphaBruh	Parrots (IOI11_parrots)	C++20	100 / 100	11 ms	840 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];
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;
void enc(int len, short ele, ll rnk){
    if(len==0) return;
    while(rnk>=C(15-ele+len-1,15-ele)){
        rnk-=C(15-ele+len-1,15-ele);
        ele++;
    }
    multi[mid++]=ele;
    enc(len-1,ele,rnk);
}
void SD(int prf,ll msg){
    int len=0;
    while(msg>=C(16+len,16)) len++;
    if(len==0) return;
    msg-=C(15+len,16);
    mid=0;
    enc(len,0,msg);
    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];
    for(int id=0;id*4<N;id++){
        int st=id*4;
        sm[id]=0;
        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;
}

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;
}
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);
    for(int id=0;id<16;id++){
        DC(id);
        for(int i=(id<<2);i<=((id<<2)|3);i++){
            M[i]=(SM[id]&255);
            SM[id]>>=8;
        }
    }
    for(int i=0;i<N;i++) output(M[i]);
}

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