Submission #565619

#	Time	Username	Problem	Language	Result	Execution time	Memory
565619		qwerasdfzxcl	Parrots (IOI11_parrots)	C++14	100 / 100	84 ms	114616 KiB

encoder

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

using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct BigInt{
    ll a[20];
    BigInt(){fill(a, a+20, 0);}
    BigInt(ll x){a[0] = x; fill(a+1, a+20, 0);}

    void print(char _end = 0){
        char buf[360];
        for (int i=0;i<20;i++){
            ll tmp = a[i];
            for (int j=0;j<18;j++){
                buf[i*18+j] = tmp%10 + '0';
                tmp /= 10;
            }
        }
        bool flag = 0;
        for (int i=359;i>=0;i--){
            if (!flag){
                if (buf[i]!='0') flag = 1;
                else continue;
            }
            printf("%c", buf[i]);
        }
        if (!flag) printf("0");
        if (_end) printf("%c", _end);
    }

    bool operator < (const BigInt &B) const{
        for (int i=19;i>=0;i--){
            if (a[i] < B.a[i]) return true;
            else if (a[i] > B.a[i]) return false;
        }
        return false;
    }

    BigInt operator + (const BigInt &B) const{
        BigInt ret = *this;
        bool carry = 0;
        for (int i=0;i<20;i++){
            if (carry) ret.a[i]++;
            ret.a[i] += B.a[i];
            if (ret.a[i] >= INF) ret.a[i] -= INF, carry = 1;
            else carry = 0;
        }
        assert(!carry);
        //for (int i=0;i<20;i++) printf("%lld ", ret.a[i]);
        //printf("\n");
        return ret;
    }

    BigInt operator - (const BigInt &B) const{
        BigInt ret = *this;
        bool carry = 0;

        for (int i=0;i<20;i++){
            ll cur = B.a[i];
            if (carry) cur++;
            if (ret.a[i] < cur){
                ret.a[i] += INF;
                carry = 1;
            }
            else carry = 0;

            ret.a[i] -= cur;
        }
        assert(!carry);
        return ret;
    }
};
static BigInt comb[601][601], pw[601];

static void init(){
    if (comb[0][0].a[0]) return;
    for (int i=0;i<=600;i++){
        comb[i][0] = BigInt(1);
        comb[i][i] = BigInt(1);
        for (int j=1;j<i;j++) comb[i][j] = comb[i-1][j] + comb[i-1][j-1];

        if (i) pw[i] = pw[i-1] + pw[i-1];
        else pw[i] = BigInt(1);
    }
    //pw[600].print('\n');
    //comb[600][300].print('\n');
    //(pw[600]-comb[600][300]).print('\n');
}

static BigInt H(int n, int r){
    return comb[n+r-1][r];
}

void encode(int N, int M[])
{
    init();
    BigInt _code;
    for (int i=0;i<N;i++){
        for (int j=0;j<8;j++) if (M[i]&(1<<j)){
            _code = _code + pw[i*8+j];
        }
    }
    //_code.print('\n');

    int cur = 0;
    for (int i=0;i<N*5;i++){
        int rem = N*5-i-1;
        while (!(_code < H(256-cur, rem))){
            _code = _code - H(256-cur, rem);
            cur++;
        }
        send(cur);
    }
    //printf("--\n");
}

decoder

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

using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct BigInt{
    ll a[20];
    BigInt(){fill(a, a+20, 0);}
    BigInt(ll x){a[0] = x; fill(a+1, a+20, 0);}

    void print(char _end = 0){
        char buf[360];
        for (int i=0;i<20;i++){
            ll tmp = a[i];
            for (int j=0;j<18;j++){
                buf[i*18+j] = tmp%10 + '0';
                tmp /= 10;
            }
        }
        bool flag = 0;
        for (int i=359;i>=0;i--){
            if (!flag){
                if (buf[i]!='0') flag = 1;
                else continue;
            }
            printf("%c", buf[i]);
        }
        if (!flag) printf("0");
        if (_end) printf("%c", _end);
    }

    bool operator < (const BigInt &B) const{
        for (int i=19;i>=0;i--){
            if (a[i] < B.a[i]) return true;
            else if (a[i] > B.a[i]) return false;
        }
        return false;
    }

    BigInt operator + (const BigInt &B) const{
        BigInt ret = *this;
        bool carry = 0;
        for (int i=0;i<20;i++){
            if (carry) ret.a[i]++;
            ret.a[i] += B.a[i];
            if (ret.a[i] >= INF) ret.a[i] -= INF, carry = 1;
            else carry = 0;
        }
        assert(!carry);
        //for (int i=0;i<20;i++) printf("%lld ", ret.a[i]);
        //printf("\n");
        return ret;
    }

    BigInt operator - (const BigInt &B) const{
        BigInt ret = *this;
        bool carry = 0;

        for (int i=0;i<20;i++){
            ll cur = B.a[i];
            if (carry) cur++;
            if (ret.a[i] < cur){
                ret.a[i] += INF;
                carry = 1;
            }
            else carry = 0;

            ret.a[i] -= cur;
        }
        assert(!carry);
        return ret;
    }
};
static BigInt comb[601][601], pw[601];

static void init(){
    if (comb[0][0].a[0]) return;
    for (int i=0;i<=600;i++){
        comb[i][0] = BigInt(1);
        comb[i][i] = BigInt(1);
        for (int j=1;j<i;j++) comb[i][j] = comb[i-1][j] + comb[i-1][j-1];

        if (i) pw[i] = pw[i-1] + pw[i-1];
        else pw[i] = BigInt(1);
    }
    //pw[600].print('\n');
    //comb[600][300].print('\n');
    //(pw[600]-comb[600][300]).print('\n');
}

static BigInt H(int n, int r){
    return comb[n+r-1][r];
}

static int a[1010];

void decode(int N, int L, int X[])
{
    fill(a, a+N, 0);
    init();
    sort(X, X+L);
    int cur = 0;
    BigInt _code;

    for (int i=0;i<L;i++){
        int rem = L-i-1;
        while(cur<X[i]){
            _code = _code + H(256-cur, rem);
            cur++;
        }
    }

    int pt = N*8-1;
    for (int i=N-1;i>=0;i--){
        for (int j=7;j>=0;j--){
            if (!(_code < pw[pt])){
                _code = _code - pw[pt];
                a[i] |= 1<<j;
            }
            pt--;
        }
    }
    for (int i=0;i<N;i++) output(a[i]);
}

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