Submission #100580

#	Time	Username	Problem	Language	Result	Execution time	Memory
100580		alexpetrescu	Parrots (IOI11_parrots)	C++14	100 / 100	532 ms	11248 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
//#include <cstdio>
#include <vector>

#define vec std::vector
#define ll long long

const ll MASK = (1LL << 56) - 1;

inline void aranjez(vec < ll > &a) {
    while (!a.empty() && a.back() == 0)
        a.pop_back();
}

inline void scad(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        tr += a[i];
        if (i < (int)b.size())
            tr -= b[i];
        if (tr < 0) {
            a[i] = (tr + MASK + 1) & MASK;
            tr = -1;
        } else {
            a[i] = tr;
            tr = 0;
        }
    }
    aranjez(a);
}

inline void adun(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        if (i < (int)b.size())
            tr += b[i];
        if (i < (int)a.size()) {
            tr += a[i];
            a[i] = tr & MASK;
            tr >>= 56;
        } else {
            a.push_back(tr & MASK);
            tr >>= 56;
        }
    }
}

inline bool cmp(vec < ll > &a, vec < ll > &b) {
    if (a.size() != b.size())
        return a.size() < b.size();
    int poz = a.size() - 1;
    while (poz >= 0 && a[poz] == b[poz])
        poz--;
    if (poz >= 0)
        return a[poz] < b[poz];
    else
        return 0;
}

void encode(int N, int M[]) {
    vec < ll > val;
    for (int i = N - 1; i >= 0; i -= 7) {
        ll r = M[i];
        for (int j = 1; j < 7 && i - j >= 0; j++)
            r |= (1LL * M[i - j]) << (8 * j);
        val.push_back(r);
    }
    aranjez(val);
    if (val.empty())
        return ;

    vec < ll > unu(1, 1), sum(1, 256);
    vec < vec < ll > > lin(256, unu);
    vec < vec < vec < ll > > > dp(1, lin);
    int n = 1;
    while (cmp(sum, val)) {
        n++;
        scad(val, sum);
        sum.clear();
        for (int j = 254; j >= 0; j--)
            adun(lin[j], lin[j + 1]);
        for (int j = 0; j < 256; j++)
            adun(sum, lin[j]);
        dp.push_back(lin);
    }
    //printf("\n%f\n\n", n / (double) N);

    int cat = 0;
    for (int i = 1; i <= n; i++) {
        while (cmp(dp[n - i][cat], val)) {
            scad(val, dp[n - i][cat]);
            cat++;
        }
        send(cat);
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <vector>

#define vec std::vector
#define ll long long

const ll MASK = (1LL << 56) - 1;

inline void adun(vec < ll > &a, vec < ll > &b) {
    ll tr = 0;
    for (int i = 0; i < (int)b.size() || tr; i++) {
        if (i < (int)b.size())
            tr += b[i];
        if (i < (int)a.size()) {
            tr += a[i];
            a[i] = tr & MASK;
            tr >>= 56;
        } else {
            a.push_back(tr & MASK);
            tr >>= 56;
        }
    }
}

void decode(int N, int L, int X[]) {
    if (L == 0) {
        for (int i = 0; i < N; i++)
            output(0);
        return ;
    }
    std::sort(X, X + L);

    /*printf("I received %d element(s): ", L);
    for (int i = 0; i < L; i++)
        printf("%d ", X[i]);
    printf("\n\n");*/

    vec < ll > sum(1, 1), unu(1, 1);
    vec < vec < ll > > lin(256, unu);
    vec < vec < vec < ll > > > dp(1, lin);
    int n = 1;
    while (n < L) {
        for (int i = 0; i < 256; i++)
            adun(sum, lin[i]);
        for (int j = 254; j >= 0; j--)
            adun(lin[j], lin[j + 1]);
        dp.push_back(lin);
        n++;
    }

    int cat = 0;
    for (int i = 1; i <= n; i++) {
        while (cat < X[i - 1]) {
            adun(sum, dp[n - i][cat]);
            cat++;
        }
    }

    std::vector < int > ans(N, 0);
    int poz = 0, mask = (1 << 8) - 1;
    for (int i = N - 1; i >= 0; i -= 7) {
        ll x = 0;
        if (poz < (int)sum.size())
            x = sum[poz];
        poz++;
        ans[i] = x & mask;
        for (int j = 1; j < 7 && i - j >= 0; j++) {
            x >>= 8;
            ans[i - j] = x & mask;
        }
    }

    for (int i = 0; i < N; i++)
        output(ans[i]);
}

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