Submission #706147

#	Time	Username	Problem	Language	Result	Execution time	Memory
706147		tht2005	Parrots (IOI11_parrots)	C++17	98 / 100	8 ms	1356 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <vector>
#include <utility>

void encode(int N, int M[])
{
    std::vector<std::pair<int, int>> ONE, ZERO;
    int sum_one = 0, sum_zero = 0;
    for(int i = 0; i < N; i += 2) {
        int pos = i >> 1;
        int x = M[i], y = (i + 1 == N) ? 0 : M[i + 1];
        for(int t = 8; t--; ) {
            int cnt = (x >> t & 1) | ((y >> t & 1) << 1);
            ONE.emplace_back(cnt, (t << 5) | pos);
            ZERO.emplace_back(3 - cnt, (t << 5) | pos);
            sum_one += cnt;
            sum_zero += 3 - cnt;
        }
    }
    if(sum_one < sum_zero) {
        for(auto& [x, y] : ONE) {
            while(x--) {
                send(y);
            }
        }
        for(int t = 4; t--; ) {
            send(0);
        }
    }
    else {
        for(auto& [x, y] : ZERO) {
            while(x--) {
                send(y);
            }
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <cstring>

int cnt[8][100], res[100];

void decode(int N, int L, int X[])
{
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < L; ++i) {
        ++cnt[X[i] >> 5][X[i] & 31];
    }
    bool ONE = cnt[0][0] >= 4;
    cnt[0][0] %= 4;
    memset(res, 0, sizeof(res));
    for(int t = 8; t--; ) {
        for(int i = (N - 1) >> 1; i >= 0; --i) {
            if(!ONE) {
                cnt[t][i] = 3 - cnt[t][i];
            }
            if(cnt[t][i] & 1) {
                res[i << 1] |= 1 << t;
            }
            if(cnt[t][i] >> 1 & 1) {
                res[i << 1 | 1] |= 1 << t;
            }
        }
    }
    for(int i = 0; i < N; ++i) {
        output(res[i]);
    }
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 17 / 19