Submission #1008782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008782		biank	Parrots (IOI11_parrots)	C++14	0 / 100	2074 ms	134968 KiB

encoder

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

#define sz(x) int(x.size())
 
using ll = long long;
 
const int BASE = 1e8;
 
struct BigInt {
    vector<int> num;
    BigInt(int x = 0) {
        if (!x) num = {0};
        else {
            num = {};
            while (x) {
                num.push_back(int(x % BASE));
                x /= BASE;
            }
        }
    }
    int operator[](int i) const { return num[i]; }
    friend BigInt operator+(BigInt x, BigInt y) {
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        BigInt z;
        int carry = 0;
        for (int i = 0; i < sz(x.num); i++) {
            int s = x[i] + y[i] + carry;
            z.num.push_back(s % BASE);
            carry = s / BASE;
        }
        return z;
    }
    friend BigInt operator-(BigInt x, BigInt y) {//x >= y
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        BigInt z;
        int carry = 0;
        for (int i = 0; i < sz(x.num); i++) {
            int s = x[i] - y[i] - carry;
            if (s < 0) s += BASE, carry = 1;
            else carry = 0;
            z.num.push_back(s);
        }
        return z;
    }
    friend bool operator<(BigInt &x, BigInt &y) {
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        for (int i = sz(x.num) - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return x[i] < y[i];
        }
        return false;
    } 
    friend bool operator>=(BigInt x, BigInt y) {
        return !(x < y);
    }
    BigInt &operator+=(BigInt o) {
        return *this = *this + o;
    }
    BigInt &operator-=(BigInt o) {
        return *this = *this - o;
    }
    BigInt operator*(int y) {
        BigInt z;
        ll carry = 0;
        for (int i = 0; i < sz(num); i++) {
            ll m = 1LL * num[i] * y + carry;
            z.num.push_back(m % BASE);
            carry = m / BASE;
        }
        while (carry) {
            z.num.push_back(carry % BASE);
            carry /= BASE;
        }
        return z;
    }
};
 
const int MAXN = 320;
const int MAXA = 255;
 
BigInt dp[MAXN][MAXA];
bool flag = false;
 
void calcDP() {
    for (int i = 0; i < MAXA; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < MAXN; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < MAXA; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    flag = true;
}
 
void encode(int N, int M[]) {
    if (!flag) calcDP();
    BigInt pos = 0;
    for (int i = 0; i < N; i++) {
        pos = pos * 256 + M[i];
    }
    pos += 1;
    for (int i = 5 * N - 1; i >= 0; i--) {
        int j = 0;
        while (pos >= dp[i][j]) {
            pos -= dp[i][j];
            j++;
        }
        send(j);
    }
}

decoder

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

#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
 
using ll = long long;
 
const int BASE = 1e8;
 
struct BigInt {
    vector<int> num;
    BigInt(int x = 0) {
        if (!x) num = {0};
        else {
            num = {};
            while (x) {
                num.push_back(int(x % BASE));
                x /= BASE;
            }
        }
    }
    int operator[](int i) const { return num[i]; }
    friend BigInt operator+(BigInt x, BigInt y) {
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        BigInt z;
        int carry = 0;
        for (int i = 0; i < sz(x.num); i++) {
            int s = x[i] + y[i] + carry;
            z.num.push_back(s % BASE);
            carry = s / BASE;
        }
        return z;
    }
    friend BigInt operator-(BigInt x, BigInt y) {//x >= y
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        BigInt z;
        int carry = 0;
        for (int i = 0; i < sz(x.num); i++) {
            int s = x[i] - y[i] - carry;
            if (s < 0) s += BASE, carry = 1;
            else carry = 0;
            z.num.push_back(s);
        }
        return z;
    }
    friend bool operator<(BigInt &x, BigInt &y) {
        while (sz(x.num) < sz(y.num)) x.num.push_back(0);
        while (sz(y.num) < sz(x.num)) y.num.push_back(0);
        for (int i = sz(x.num) - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return x[i] < y[i];
        }
        return false;
    } 
    friend bool operator>=(BigInt x, BigInt y) {
        return !(x < y);
    }
    BigInt &operator+=(BigInt o) {
        return *this = *this + o;
    }
    BigInt &operator-=(BigInt o) {
        return *this = *this - o;
    }
    pair<BigInt, int> operator/(int k) {
        BigInt z;
        int carry = 0;
        for (int i = sz(num) - 1; i >= 0; i--) {
            ll m = 1LL * carry * BASE + num[i];
            if (m / k || !z.num.empty()) z.num.push_back(m / k);
            carry = m % k;
        }
        reverse(all(z.num));
        return {z, carry};
    }
};
 
 
const int MAXN_DE = 320;
const int MAXA_DE = 255;
 
BigInt dp[MAXN_DE][MAXA_DE];
bool flag = false;
 
void calcDP() {
    for (int i = 0; i < MAXA_DE; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < MAXN_DE; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < MAXA_DE; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    flag = true;
}
 
void decode(int N, int L, int X[]) {
    if (!flag) calcDP();
    sort(X, X + L);
    BigInt pos = 0;
    for (int i = L - 1; i >= 0; i--) {
        for (int j = 0; j < X[i]; j++) pos += dp[i][j];
    }
    pos -= 1;
    vector<int> res;
    for (int i = 0; i < N; i++) {
        int x;
        tie(pos, x) = pos / 256;
        res.push_back(x);
    }

    for (int i = N - 1; i >= 0; i--) {
        output(res[i]);
    }
}

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