제출 #1363278

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

encoder

#include "encoder.h"

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

#include "encoderlib.h"

using namespace std;

void encode(int N, int M[]) {
    int n = 12;
    vector<vector<int>> combs;
    map<vector<int>, int> m;

    auto gen = [&](vector<int>& v, int curIdx, auto gen) -> void {
        if (curIdx == 8)
            combs.push_back(v);
        else {
            int curCnt = accumulate(v.begin(), v.begin() + curIdx, 0);
            for (int i = 0; i <= n - curCnt; ++i) {
                v[curIdx] = i;
                gen(v, curIdx + 1, gen);
            }
        }
    };

    vector<int> curGen(8);
    gen(curGen, 0, gen);

    sort(combs.begin(), combs.end(), [](const vector<int>& a, const vector<int>& b) {
        return accumulate(a.begin(), a.end(), 0) < accumulate(b.begin(), b.end(), 0);
    });

    // mt19937 g(87365812);

    // shuffle(combs.begin(), combs.begin() + 65536, g);
    for (int i = 0; i < 65536; ++i) m[combs[i]] = i;

    for (int i = 0; i < N; i += 2) {
        int cur = i * 4, val = M[i];
        if (i < N - 1) val += M[i + 1] * 256;
        vector<int> curV = combs[val];
        for (int j = 7; j >= 0; --j) {
            while (curV[j]) {
                send(cur + j);
                --curV[j];
            }
        }
    }
}

decoder

#include "decoder.h"

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

#include "decoderlib.h"

using namespace std;

void decode(int N, int L, int X[]) {
    int n = 12;
    vector<vector<int>> combs;
    map<vector<int>, int> m;

    auto gen = [&](vector<int>& v, int curIdx, auto gen) -> void {
        if (curIdx == 8)
            combs.push_back(v);
        else {
            int curCnt = accumulate(v.begin(), v.begin() + curIdx, 0);
            for (int i = 0; i <= n - curCnt; ++i) {
                v[curIdx] = i;
                gen(v, curIdx + 1, gen);
            }
        }
    };

    vector<int> curGen(8);
    gen(curGen, 0, gen);

    sort(combs.begin(), combs.end(), [](const vector<int>& a, const vector<int>& b) {
        return accumulate(a.begin(), a.end(), 0) < accumulate(b.begin(), b.end(), 0);
    });

    // mt19937 g(87365812);

    // shuffle(combs.begin(), combs.begin() + 65536, g);
    for (int i = 0; i < 65536; ++i) m[combs[i]] = i;

    vector<vector<int>> preRes((N + 1) / 2, vector<int>(8));
    for (int i = 0; i < L; ++i) {
        int idx = X[i] / 8;
        ++preRes[idx][X[i] % 8];
    }
    for (int i = 0; i < N; i += 2) {
        int curIdx = i / 2;
        int val = m[preRes[curIdx]];
        output(val % 256);
        if (i != N - 1) output(val / 256);
    }
}

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