제출 #1364962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364962		ericl23302	앵무새 (IOI11_parrots)	C++20	17 / 100	1 ms	580 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[]) {
    vector<vector<ll>> dp(17, vector<ll>(21));
    for (int i = 0; i < 17; ++i) dp[i][0] = 1;
    for (int i = 1; i < 17; ++i) {
        for (int j = 1; j < 21; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }

    auto doSend = [&](int i, int curI, int 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 (int i = 0; i < (N + 3) / 4; ++i) {
        ll cur = 0;
        for (int j = 0; j < 4 && i * 4 + j < N; ++j) cur += (M[i * 4 + j] << (j * 8));
        int 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[]) {
    vector<vector<ll>> dp(17, vector<ll>(21));
    for (int i = 0; i < 17; ++i) dp[i][0] = 1;
    for (int i = 1; i < 17; ++i) {
        for (int 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: 0 / 17
• 서브태스크 3: 0 / 18
• 서브태스크 4: 0 / 29
• 서브태스크 5: 0 / 19