oj.uz

답안 #830902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830902 2023-08-19T12:45:25 Z PanosPask 앵무새 (IOI11_parrots) C++14
100 / 100
 182 ms 73764 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 + pref[r][BASE - 1] < num) {
        tot = tot + pref[r][BASE - 1];
        r++;
    }

    while (tot + dp[r][c] < num) {
        tot = tot + dp[r][c];
        c++;
    }

    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.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 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 - 1; r++)
        num = num + pref[r][BASE - 1];
    if (X[0])
        num = num + pref[L - 1][X[0] - 1];

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 73224 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 73448 KB Output is correct
2 Correct 142 ms 73532 KB Output is correct
3 Correct 147 ms 73420 KB Output is correct
4 Correct 144 ms 73560 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 73508 KB Output is correct
2 Correct 142 ms 73536 KB Output is correct
3 Correct 144 ms 73516 KB Output is correct
4 Correct 147 ms 73416 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 73540 KB Output is correct
2 Correct 141 ms 73564 KB Output is correct
3 Correct 143 ms 73476 KB Output is correct
4 Correct 152 ms 73548 KB Output is correct
5 Correct 155 ms 73568 KB Output is correct
6 Correct 150 ms 73576 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 73516 KB Output is correct - P = 1.750000
2 Correct 153 ms 73524 KB Output is correct - P = 2.437500
3 Correct 150 ms 73528 KB Output is correct - P = 2.484848
4 Correct 163 ms 73764 KB Output is correct - P = 3.280000
5 Correct 179 ms 73660 KB Output is correct - P = 3.833333
6 Correct 182 ms 73724 KB Output is correct - P = 4.015873
7 Correct 182 ms 73752 KB Output is correct - P = 4.078125