oj.uz

Submission #1008800

# Submission time Handle Problem Language Result Execution time Memory
1008800 2024-06-26T18:45:05 Z biank Parrots (IOI11_parrots) C++14
100 / 100
 677 ms 16468 KB 
#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) {
        num = {};
        while (x) {
            num.push_back(int(x % BASE));
            x /= BASE;
        }
    }
    int operator[](int i) const {
        if (i >= sz(num)) return 0;
        return num[i];
    }
    friend BigInt operator+(const BigInt &x, const BigInt &y) {
        BigInt z;
        int carry = 0;
        int d = max(sz(x.num), sz(y.num));
        for (int i = 0; i < d; i++) {
            int s = x[i] + y[i] + carry;
            z.num.push_back(s % BASE);
            carry = s / BASE;
        }
        while (carry) {
            z.num.push_back(carry % BASE);
            carry /= BASE;
        }
        return z;
    }
    friend BigInt operator-(BigInt x, BigInt y) {//x >= y
        BigInt z;
        int carry = 0;
        int d = max(sz(x.num), sz(y.num));
        for (int i = 0; i < d; i++) {
            int s = x[i] - y[i] - carry;
            if (s < 0) s += BASE, carry = 1;
            else carry = 0;
            z.num.push_back(s);
        }
        while (sz(z.num) > 1 && z.num.back() == 0) z.num.pop_back();
        return z;
    }
    friend bool operator<(const BigInt &x, const BigInt &y) {
        int d = max(sz(x.num), sz(y.num));
        for (int i = d - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return x[i] < y[i];
        }
        return false;
    } 
    friend bool operator>=(const BigInt x, const BigInt y) {
        return !(x < y);
    }
    BigInt &operator+=(const BigInt &o) {
        return *this = *this + o;
    }
    BigInt &operator-=(const 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;
    }
};
 
BigInt dp[320][255];
bool flag = false;
 
void calcDP() {
    for (int i = 0; i < 255; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < 320; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < 255; 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);
    }
}

#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 BASE2 = 1e8;
 
struct BigInt2 {
    vector<int> num;
    BigInt2(int x = 0) {
        num = {};
        while (x) {
            num.push_back(int(x % BASE2));
            x /= BASE2;
        }
    }
    int operator[](int i) const {
        if (i >= sz(num)) return 0;
        return num[i];
    }
    friend BigInt2 operator+(const BigInt2 &x, const BigInt2 &y) {
        BigInt2 z;
        int carry = 0;
        int d = max(sz(x.num), sz(y.num));
        for (int i = 0; i < d; i++) {
            int s = x[i] + y[i] + carry;
            z.num.push_back(s % BASE2);
            carry = s / BASE2;
        }
        while (carry) {
            z.num.push_back(carry % BASE2);
            carry /= BASE2;
        }
        return z;
    }
    friend BigInt2 operator-(BigInt2 x, BigInt2 y) {//x >= y
        BigInt2 z;
        int d = max(sz(x.num), sz(y.num));
        int carry = 0;
        for (int i = 0; i < d; i++) {
            int s = x[i] - y[i] - carry;
            if (s < 0) s += BASE2, carry = 1;
            else carry = 0;
            z.num.push_back(s);
        }
        while (sz(z.num) > 1 && z.num.back() == 0) z.num.pop_back();
        return z;
    }
    friend bool operator<(const BigInt2 &x, const BigInt2 &y) {
        int d = max(sz(x.num), sz(y.num));
        for (int i = d - 1; i >= 0; i--) {
            if (x[i] ^ y[i]) return x[i] < y[i];
        }
        return false;
    } 
    friend bool operator>=(const BigInt2 &x, const BigInt2 &y) {
        return !(x < y);
    }
    BigInt2 &operator+=(BigInt2 o) {
        return *this = *this + o;
    }
    BigInt2 &operator-=(BigInt2 o) {
        return *this = *this - o;
    }
    pair<BigInt2, int> operator/(int k) {
        BigInt2 z;
        int carry = 0;
        for (int i = sz(num) - 1; i >= 0; i--) {
            ll m = 1LL * carry * BASE2 + num[i];
            if (m / k || !z.num.empty()) z.num.push_back(m / k);
            carry = m % k;
        }
        reverse(all(z.num));
        return {z, carry};
    }
};
 
BigInt2 dp2[320][255];
bool flag2 = false;
 
void calcdp22() {
    for (int i = 0; i < 255; i++) {
        dp2[0][i] = 1;
    }
    for (int i = 1; i < 320; i++) {
        dp2[i][0] = dp2[i - 1][0];
        for (int j = 1; j < 255; j++) {
            dp2[i][j] = dp2[i - 1][j] + dp2[i][j - 1];
        }
    }
    flag2 = true;
}
 
void decode(int N, int L, int X[]) {
    if (!flag2) calcdp22();
    sort(X, X + L);
    BigInt2 pos = 0;
    for (int i = L - 1; i >= 0; i--) {
        for (int j = 0; j < X[i]; j++) pos += dp2[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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15552 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16164 KB Output is correct
2 Correct 34 ms 16152 KB Output is correct
3 Correct 62 ms 16148 KB Output is correct
4 Correct 55 ms 16348 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16164 KB Output is correct
2 Correct 34 ms 16064 KB Output is correct
3 Correct 46 ms 16156 KB Output is correct
4 Correct 46 ms 16172 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16172 KB Output is correct
2 Correct 50 ms 16056 KB Output is correct
3 Correct 81 ms 16016 KB Output is correct
4 Correct 127 ms 16036 KB Output is correct
5 Correct 131 ms 16060 KB Output is correct
6 Correct 184 ms 16084 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16148 KB Output is correct
2 Correct 142 ms 16088 KB Output is correct
3 Correct 151 ms 16096 KB Output is correct
4 Correct 345 ms 16108 KB Output is correct
5 Correct 545 ms 16208 KB Output is correct
6 Correct 627 ms 16468 KB Output is correct
7 Correct 677 ms 16132 KB Output is correct