Submission #595217

#	Time	Username	Problem	Language	Result	Execution time	Memory
595217		Bench0310	Parrots (IOI11_parrots)	C++17	100 / 100	7 ms	1348 KiB

encoder

#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"

using namespace std;
typedef long long ll;

static const int S=20;
static ll C[2*S+1][2*S+1];

static void ini()
{
    for(int i=0;i<=2*S;i++) C[i][0]=1;
    for(int i=1;i<=2*S;i++) for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}

static ll opt(int n,int m){return C[n+m-1][n];}

array<int,16> enc(array<int,4> a,int cnt)
{
    reverse(a.begin(),a.end());
    ll b=0;
    for(int i=0;i<4;i++) b=(b<<8)+a[i];
    array<int,16> c;
    c.fill(0);
    for(int i=0;i<16;i++)
    {
        while(cnt>0&&opt(cnt,16-i)<=b)
        {
            b-=opt(cnt,16-i);
            c[i]++;
            cnt--;
        }
    }
    assert(b==0);
    return c;
}

void encode(int N,int M[])
{
    ini();
    for(int i=0;i<N;i+=4)
    {
        array<int,4> a;
        a.fill(0);
        for(int j=0;j<4&&i+j<N;j++) a[j]=M[i+j];
        array<int,16> c=enc(a,5*min(4,N-i));
        for(int j=0;j<16;j++) for(int k=0;k<c[j];k++) send(((i>>2)<<4)+j);
    }
}

decoder

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"

using namespace std;
typedef long long ll;

static const int S=20;
static ll C[2*S+1][2*S+1];

static void ini()
{
    for(int i=0;i<=2*S;i++) C[i][0]=1;
    for(int i=1;i<=2*S;i++) for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}

static ll opt(int n,int m){return C[n+m-1][n];}

array<int,4> dec(array<int,16> c,int cnt)
{
    ll b=0;
    for(int i=0;i<16;i++)
    {
        while(c[i]--)
        {
            b+=opt(cnt,16-i);
            cnt--;
        }
    }
    array<int,4> a;
    for(int i=3;i>=0;i--)
    {
        a[i]=(b&255);
        b>>=8;
    }
    reverse(a.begin(),a.end());
    return a;
}

void decode(int N,int L,int X[])
{
    ini();
    vector<array<int,16>> v(N);
    for(int i=0;i<N;i++) v[i].fill(0);
    for(int i=0;i<L;i++)
    {
        int x=X[i];
        v[(x>>4)<<2][x&15]++;
    }
    for(int i=0;i<N;i+=4)
    {
        array<int,4> a=dec(v[i],5*min(4,N-i));
        for(int j=0;j<4&&i+j<N;j++) output(a[j]);
    }
}

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