oj.uz

Submission #830887

# Submission time Handle Problem Language Result Execution time Memory
830887 2023-08-19T12:35:59 Z PanosPask Parrots (IOI11_parrots) C++14
81 / 100
 2000 ms 73848 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <vector>
#include <iostream>

using namespace std;

struct BigNum {
    const int BASE = 256;

    // The higher order is back to front
    vector<int> num;

    BigNum(vector<int>& a) {
        num = a;
    }
    BigNum(int a) {
        while (a) {
            num.push_back(a % BASE);
            a /= BASE;
        }
    }
    BigNum(void) {
        ;
    }

    int size(void) {
        return this->num.size();
    }

    bool operator < (const BigNum L) {
        if (this->num.size() < L.num.size())
            return true;
        else if (this->num.size() > L.num.size())
            return false;

        for (int i = L.num.size() - 1; i >= 0; i--) {
            int a = this->num[i];
            int b = L.num[i];

            if (a < b)
                return true;
            if (b < a)
                return false;
        }

        return false;
    }
    bool operator == (BigNum L) {
        return !(*this < L) && !(L < *this);
    }
    bool operator <= (BigNum L) {
        return (*this < L) || (*this == L);
    }
    bool operator > (BigNum L) {
        return !(*this <= L);
    }
    bool operator >= (BigNum L) {
        return !(*this < L);
    }

    void operator = (BigNum L) {
        this->num = L.num;
    }

    BigNum operator + (BigNum L) {
        BigNum c;
        int keep = 0;
        for (int i = 0; i < max(L.size(), this->size()); i++) {
            int v = keep;
            keep = 0;
            if (i < L.size())
                v += L.num[i];
            if (i < this->size())
                v += this->num[i];

            if (v >= BASE) {
                keep = 1;
                v -= BASE;
            }
            c.num.push_back(v);
        }
        if (keep)
            c.num.push_back(keep);

        return c;
    }

    BigNum operator - (BigNum L) {
        BigNum c;
        int rem = 0;
        for (int i = 0; i < this->size(); i++) {
            int v = this->num[i] - rem;
            rem = 0;
            if (i < L.size())
                v -= L.num[i];

            if (v < 0) {
                v += BASE;
                rem = 1;
            }

            c.num.push_back(v);
        }
        while (c.size() && c.num.back() == 0)
            c.num.pop_back();

        return c;
    }
};

static int BASE = 256;
static int TOP = 400;

// dp[i][j]: Number of sequences of length i + 1 that start with j
static vector<vector<BigNum>> dp;

// pref[i][j]: Number of sequences of length i + 1 and first number at most j
static vector<vector<BigNum>> pref;

static bool done = false;

static void calculate_dp(void)
{
    dp.assign(TOP, vector<BigNum>(BASE, (BigNum)(0)));
    pref.resize(TOP, vector<BigNum>(BASE));
    for (int i = 0; i < TOP; i++) {
        for (int j = 0; j < BASE; j++) {
            if (i) {
                dp[i][j] = pref[i - 1][j];
            }
            else {
                dp[0][j] = 1;
            }
        }
        pref[i][0] = dp[i][0];
        for (int j = 1; j < BASE; j++) {
            pref[i][j] = dp[i][j] + pref[i][j - 1];
        }
    }
}

void construct_sequence(BigNum num, int MAXC, int r)
{
    if (r == 0) {
        send(num.num[0] - 1);
        return;
    }

    int c = MAXC;

    while (c >= 0 && pref[r][c] >= num)
        c--;
    if (c >= 0) {
        num = num - pref[r][c];
    }
    c++;

    send(c);

    construct_sequence(num, c, r - 1);

}

void encode(int N, int M[])
{
    if (!done) {
        calculate_dp();
        done = true;
    }

    int i;
    vector<int> v;
    for(i=0; i<N; i++)
        v.push_back(M[i]);

    while (v.size() && v.back() == 0)
        v.pop_back();

    BigNum num(v);
    BigNum b(1);
    num = num + b;

    BigNum tot(0);
    int r = 0;
    int c = 0;
    while (tot + dp[r][c] < num) {
        tot = tot + dp[r][c];
        c++;
        if (c == BASE) {
            r++;
            c = 0;
        }
    }

    num = num - tot;
    send(c);

    if (r != 0)
        construct_sequence(num, c, r - 1);
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

struct BigNum {
    const int BASE = 256;

    // The higher order is back to front
    vector<int> num;

    BigNum(vector<int>& a) {
        num = a;
    }
    BigNum(int a) {
        while (a) {
            num.push_back(a % BASE);
            a /= BASE;
        }
    }
    BigNum(void) {
        ;
    }

    int size(void) {
        return this->num.size();
    }

    bool operator < (const BigNum& L) {
        if (this->num.size() < L.num.size())
            return true;
        else if (this->num.size() > L.num.size())
            return false;

        for (int i = L.num.size() - 1; i >= 0; i--) {
            int a = this->num[i];
            int b = L.num[i];

            if (a < b)
                return true;
            if (b < a)
                return false;
        }

        return false;
    }
    bool operator == (BigNum& L) {
        return !(*this < L) && !(L < *this);
    }
    bool operator <= (BigNum& L) {
        return (*this < L) || (*this == L);
    }
    bool operator > (BigNum& L) {
        return !(*this <= L);
    }
    bool operator >= (BigNum& L) {
        return !(*this < L);
    }

    void operator = (BigNum L) {
        this->num = L.num;
    }

    BigNum operator + (BigNum& L) {
        BigNum c;
        int keep = 0;
        for (int i = 0; i < max(L.size(), this->size()); i++) {
            int v = keep;
            keep = 0;
            if (i < L.size())
                v += L.num[i];
            if (i < this->size())
                v += this->num[i];

            if (v >= BASE) {
                keep = 1;
                v -= BASE;
            }
            c.num.push_back(v);
        }
        if (keep)
            c.num.push_back(keep);

        return c;
    }

    BigNum operator - (BigNum& L) {
        BigNum c;
        int rem = 0;
        for (int i = 0; i < this->size(); i++) {
            int v = this->num[i] - rem;
            rem = 0;
            if (i < L.size())
                v -= L.num[i];

            if (v < 0) {
                v += BASE;
                rem = 1;
            }

            c.num.push_back(v);
        }
        while (c.num.back() == 0)
            c.num.pop_back();

        return c;
    }
};

static int BASE = 256;
static int TOP = 400;

// dp[i][j] : Number of sequences of length i with the first number beeing AT MOST
static vector<vector<BigNum>> dp;
static vector<vector<BigNum>> pref;

static bool done = false;

static void calculate_dp(void)
{
    dp.assign(TOP, vector<BigNum>(BASE, (BigNum)(0)));
    pref.resize(TOP, vector<BigNum>(BASE));
    for (int i = 0; i < TOP; i++) {
        for (int j = 0; j < BASE; j++) {
            if (i) {
                dp[i][j] = pref[i - 1][j];
            }
            else {
                dp[0][j] = 1;
            }
        }
        pref[i][0] = dp[i][0];
        for (int j = 1; j < BASE; j++) {
            pref[i][j] = dp[i][j] + pref[i][j - 1];
        }
    }
}

// Returns the number of all sequences of length r with maximum number LESS THAN c
BigNum count(int r, int c)
{
    if (!c)
        return BigNum(0);
    return pref[r][c - 1];
}

void decode(int N, int L, int X[])
{
    if (!done) {
        calculate_dp();
        done = true;
    }


    sort(X, X + L);
    reverse(X, X + L);

    BigNum num(0);
    for (int r = 0; r < L; r++)
        for (int c = 0; c < BASE; c++) {
            if (r == L - 1 && c == X[0])
                break;

            num = num + dp[r][c];
        }
    for (int i = 1; i < L; i++) {
        BigNum c = count(L - i - 1, X[i]);
        num = num + c;
    }

    // BigNum b(1);
    // num = num - b;

    while (num.size() < N)
        num.num.push_back(0);
    for (int i = 0; i < N; i++)
        output(num.num[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 73052 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 73516 KB Output is correct
2 Correct 237 ms 73416 KB Output is correct
3 Correct 317 ms 73532 KB Output is correct
4 Correct 328 ms 73544 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 73520 KB Output is correct
2 Correct 238 ms 73572 KB Output is correct
3 Correct 315 ms 73476 KB Output is correct
4 Correct 330 ms 73560 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 73736 KB Output is correct
2 Correct 334 ms 73568 KB Output is correct
3 Correct 436 ms 73580 KB Output is correct
4 Correct 821 ms 73808 KB Output is correct
5 Correct 862 ms 73648 KB Output is correct
6 Correct 905 ms 73668 KB Output is correct

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 73536 KB Output is correct - P = 1.750000
2 Correct 917 ms 73700 KB Output is correct - P = 2.437500
3 Correct 967 ms 73672 KB Output is correct - P = 2.484848
4 Execution timed out 2420 ms 73848 KB Time limit exceeded
5 Execution timed out 2066 ms 37108 KB Time limit exceeded
6 Execution timed out 2075 ms 36992 KB Time limit exceeded
7 Execution timed out 2082 ms 37004 KB Time limit exceeded