Submission #769399

#	Time	Username	Problem	Language	Result	Execution time	Memory
769399		MilosMilutinovic	Parrots (IOI11_parrots)	C++14	100 / 100	1387 ms	104196 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int C = 160;
const int B = 256;
const int N = 5 * 64;

struct NumBig {
    int d[C];
    void init() { for (int i = 0; i < C; i++) d[i] = 0; }
    NumBig() { init(); }
    void print() {
        for (int i = 0; i < 50; i++) {
            printf("%d ", d[i]);
        }
        printf("\n");
    }
};
NumBig const operator + (NumBig a, NumBig b) {
    NumBig res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] + b.d[i];
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
NumBig const operator * (NumBig a, int c) {
    //printf("mnozim sa %d\n", c);
    NumBig res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] * c;
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
bool const operator >= (NumBig a, NumBig b) {
    for (int i = C - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) {
            return a.d[i] > b.d[i];
        }
    }
    return true;
}
NumBig const operator - (NumBig a, NumBig b) {
    NumBig res;
    for (int i = 0; i < C; i++) {
        res.d[i] = a.d[i] - b.d[i];
        while (res.d[i] < 0) {
            res.d[i] += 10;
            a.d[i + 1] -= 1;
        }
    }
    return res;
}

NumBig pd[N][B];

void dp_make(int n) {
    for (int i = 0; i < B; i++) {
        pd[n - 1][i].init();
        pd[n - 1][i].d[0] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        NumBig sum;
        for (int j = B - 1; j >= 0; j--) {
            sum = sum + pd[i + 1][j];
            pd[i][j] = sum;
        }
    }
}

void encode(int N, int M[])
{
    if (pd[N - 1][0].d[0] == 0)
        dp_make(5 * N);
    NumBig val, pw;
    pw.d[0] = 1;
    for (int i = 0; i < N; i++) {
        val = val + (pw * M[i]);
        pw = pw * B;
    }
    NumBig ONE;
    ONE.d[0] = 1;
    val = val + ONE;
    int lst = 0;
    NumBig cur_sum;
    for (int i = 0; i < 5 * N; i++) {
        for (int j = lst; j < B; j++) {
            if (pd[i][j] >= val) {
                lst = j;
                send(lst);
                break;
            }
            val = val - pd[i][j];
        }
    }
}

/*
8
1 0 1 0 0 1 1 0
*/

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int C = 160;
const int B = 256;
const int N = 5 * 64;

struct BigNum {
    int d[C];
    void init() { for (int i = 0; i < C; i++) d[i] = 0; }
    BigNum() {  init();  }
    void print() {
        for (int i = 0; i < 50; i++) {
            printf("%d ", d[i]);
        }
        printf("\n");
    }
};
BigNum const operator + (BigNum a, BigNum b) {
    BigNum res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] + b.d[i];
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
BigNum const operator * (BigNum a, int c) {
//    printf("mnozim sa %d\n", c);
    BigNum res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] * c;
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
bool const operator >= (BigNum a, BigNum b) {
    for (int i = C - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) {
            return a.d[i] > b.d[i];
        }
    }
    return true;
}
BigNum const operator - (BigNum a, BigNum b) {
    BigNum res;
    for (int i = 0; i < C; i++) {
        res.d[i] = a.d[i] - b.d[i];
        while (res.d[i] < 0) {
            res.d[i] += 10;
            a.d[i + 1] -= 1;
        }
    }
    return res;
}

BigNum dp[N][B];

void make_dp(int n) {
    for (int i = 0; i < B; i++) {
        dp[n - 1][i].init();
        dp[n - 1][i].d[0] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        BigNum sum;
        for (int j = B - 1; j >= 0; j--) {
            sum = sum + dp[i + 1][j];
            dp[i][j] = sum;
        }
    }
}

BigNum bpw[N];

void decode(int N, int L, int X[])
{
    sort(X, X + L);
//    printf("got decode seq = ");
//    for (int i = 0; i < L; i++)
//        printf("%d ", X[i]);
//    printf("\n");
    if (dp[L - 1][0].d[0] == 0)
        make_dp(L);
    BigNum val;
    int lst = 0;
    for (int i = 0; i < L; i++) {
        while (lst != X[i]) {
            val = val + dp[i][lst];
            lst += 1;
        }
    }
    bpw[0].d[0] = 1;
    for (int i = 1; i < N; i++) {
        bpw[i] = bpw[i - 1] * B;
    }
//    printf("SEQ VAL = ");
//    val.print();
    vector<int> ans;
    for (int i = N - 1; i >= 0; i--) {
        ans.push_back(0);
        BigNum nm = bpw[i];
        while (val >= nm) {
            ans.back() += 1;
            nm = nm + bpw[i];
        }
        nm = nm - bpw[i];
        val = val - nm;
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans)
        output(x);
//  int i, b;
//  for(i=0; i<L; i++) {
//    b = X[i];
//    output(b);
//  }
}

/*
8
1 0 1 0 0 1 1 0

10
1 1 2 1 2 3 1 7 10 9

*/

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