Submission #51373

#	Time	Username	Problem	Language	Result	Execution time	Memory
51373		imeimi2000	Parrots (IOI11_parrots)	C++17	100 / 100	290 ms	112568 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

static const int mx = 256 + 320;

namespace enc {
    const int t = 80;
    struct bigint {
        int dat[t];
        bigint& operator+=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] += x.dat[i];
                if (i + 1 < t) {
                    dat[i + 1] += (dat[i] >> 8);
                    dat[i] &= 255;
                }
            }
            return *this;
        }
        bigint& operator-=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] -= x.dat[i];
                if (dat[i] < 0) {
                    if (i + 1 < t) --dat[i + 1];
                    dat[i] += 256;
                }
            }
            return *this;
        }
        bool operator<=(const bigint &x) const {
            for (int i = t; i--; ) {
                if (dat[i] < x.dat[i]) return 1;
                if (dat[i] > x.dat[i]) return 0;
            }
            return 1;
        }
    };
}

using namespace enc;

static bigint nCr[mx][mx];
static bool ch = 1;

static void wr() {
    nCr[0][0].dat[0] = 1;
    for (int i = 1; i < mx; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
}

static bigint& nHr(int n, int r) {
    return nCr[n + r - 1][r];
}

static int cnt[256];
void encode(int n, int msg[]) {
    if (ch) {
        ch = 0;
        wr();
    }
    for (int i = 0; i < 256; ++i) cnt[i] = 0;
    bigint m;
    for (int i = 0; i < n; ++i) {
        m.dat[i] = msg[i];
    }
    for (int i = n; i < t; ++i) {
        m.dat[i] = 0;
    }
    int c = 5 * n;
    for (int i = 0; i < 256; ++i) {
        while (nHr(256 - i, c) <= m) {
            m -= nHr(256 - i, c--);
            ++cnt[i];
        }
    }
    for (int i = 0; i < 256; ++i) {
        for (int j = 0; j < cnt[i]; ++j) {
            send(i);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"

static const int mx = 256 + 320;

namespace dec {
    const int t = 80;
    struct bigint {
        int dat[t];
        bigint& operator+=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] += x.dat[i];
                if (i + 1 < t) {
                    dat[i + 1] += (dat[i] >> 8);
                    dat[i] &= 255;
                }
            }
            return *this;
        }
        bigint& operator-=(const bigint &x) {
            for (int i = 0; i < t; ++i) {
                dat[i] -= x.dat[i];
                if (dat[i] < 0) {
                    if (i + 1 < t) --dat[i + 1];
                    dat[i] += 256;
                }
            }
            return *this;
        }
        bool operator<=(const bigint &x) const {
            for (int i = t; i--; ) {
                if (dat[i] < x.dat[i]) return 1;
                if (dat[i] > x.dat[i]) return 0;
            }
            return 1;
        }
    };
}

using namespace dec;

static bigint nCr[mx][mx];
static bool ch = 1;

static void wr() {
    nCr[0][0].dat[0] = 1;
    for (int i = 1; i < mx; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
}

static bigint& nHr(int n, int r) {
    return nCr[n + r - 1][r];
}

static int cnt[256];

void decode(int n, int l, int x[]) {
    if (ch) {
        ch = 0;
        wr();
    }
    for (int i = 0; i < 256; ++i) cnt[i] = 0;
    bigint m;
    for (int i = 0; i < t; ++i) m.dat[i] = 0;
    int c = 5 * n - l;
    for (int i = 0; i < l; ++i) {
        ++cnt[x[i]];
    }
    for (int i = 256; i--; ) {
        while (cnt[i]--) {
            m += nHr(256 - i, ++c);
        }
    }
    for (int i = 0; i < n; ++i) {
        output(m.dat[i]);
    }
}

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