제출 #1364989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364989		ericl23302	앵무새 (IOI11_parrots)	C++20	100 / 100	5 ms	836 KiB

encoder

#include "encoder.h"

#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <unordered_map>
#include <vector>

#include "encoderlib.h"

using namespace std;

using ll = long long;

void encode(int N, int M[]) {
    ll n = N;
    vector<ll> m;
    for (ll i = 0; i < n; ++i) m.push_back(M[i]);
    vector<vector<ll>> dp(17, vector<ll>(21));
    for (ll i = 0; i < 17; ++i) dp[i][0] = 1;
    for (ll i = 1; i < 17; ++i) {
        for (ll j = 1; j < 21; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }

    auto doSend = [&](ll i, ll curI, ll curJ, ll cur, auto doSend) -> void {
        if (!curJ) return;
        if (cur > dp[curI - 1][curJ]) {
            send((i << 4) + curI - 1);
            doSend(i, curI, curJ - 1, cur - dp[curI - 1][curJ], doSend);
        } else
            doSend(i, curI - 1, curJ, cur, doSend);
    };

    for (ll i = 0; i < (n + 3) / 4; ++i) {
        ll cur = 0;
        for (ll j = 0; j < 4 && i * 4 + j < n; ++j) cur += (m[i * 4 + j] << (j * 8));
        ll curJ = 0, curAdd = 0;
        while (curAdd + dp[16][curJ] <= cur) curAdd += dp[16][curJ++];
        doSend(i, 16, curJ, cur + 1 - curAdd, doSend);
    }
}

decoder

#include "decoder.h"

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <unordered_map>
#include <vector>

#include "decoderlib.h"

using namespace std;

using ll = long long;

void decode(int N, int L, int X[]) {
    ll n = N, l = L;
    vector<ll> x;
    for (ll i = 0; i < l; ++i) x.push_back(X[i]);
    vector<vector<ll>> dp(17, vector<ll>(21));
    for (ll i = 0; i < 17; ++i) dp[i][0] = 1;
    for (ll i = 1; i < 17; ++i) {
        for (ll j = 1; j < 21; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }

    vector<vector<ll>> cnts((n + 3) / 4);
    for (int i = 0; i < l; ++i) cnts[(x[i] >> 4)].push_back(x[i] % 16);
    for (int i = 0; i < (n + 3) / 4; ++i) {
        sort(cnts[i].begin(), cnts[i].end());
        ll cur = 0, sz = cnts[i].size();
        for (int j = 0; j < sz; ++j) cur += dp[cnts[i][j]][j + 1] + dp[16][j];
        for (int j = 0; j < 4 && i * 4 + j < n; ++j) output(cur % 256), cur >>= 8;
    }
}

• 서브태스크 1: 17 / 17
• 서브태스크 2: 17 / 17
• 서브태스크 3: 18 / 18
• 서브태스크 4: 29 / 29
• 서브태스크 5: 19 / 19