제출 #518480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518480		tabr	Parrots (IOI11_parrots)	C++17	0 / 100	2096 ms	332 KiB

encoder

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#define encoder

const int N = 600;

void add(bitset<N>& a, const bitset<N>& b) {
    int c = 0;
    for (int i = 0; i < N; i++) {
        int nc = (a[i] & b[i]) | (b[i] & c) | (c & a[i]);
        if (b[i] ^ c) {
            a[i].flip();
        }
        c = nc;
    }
}

bitset<N> f(const vector<int>& b) {
    vector<bitset<N>> dp(256);
    for (int i = 0; i < b[0]; i++) {
        dp[i] = bitset<N>(1);
    }
    for (int i = 0; i < (int) b.size(); i++) {
        vector<bitset<N>> new_dp(256);
        for (int j = 0; j < 256; j++) {
            for (int k = j; k < 256; k++) {
                add(new_dp[k], dp[j]);
            }
        }
        for (int j = b[i]; j < 256; j++) {
            add(new_dp[j], bitset<N>(1));
        }
        swap(dp, new_dp);
    }
    bitset<N> res;
    for (int i = 0; i < 256; i++) {
        add(res, dp[i]);
    }
    return res;
}

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

void encode(int n, int a[]) {
    bitset<N> x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 8; j++) {
            if (a[i] & (1 << j)) {
                x[i * 8 + j].flip();
            }
        }
    }
    vector<int> b(n * 5);
    for (int i = 0; i < n * 5; i++) {
        int low = 0;
        int high = 256;
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            b[i] = mid;
            bitset<N> y = f(b);
            y.flip();
            add(y, x);
            if (y[N - 1]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        b[i] = low;
    }
    for (int i = 0; i < n * 5; i++) {
        send(b[i]);
    }
    assert(f(b) == x);
}
#endif

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

void decode(int n, int l, int a[]) {
    vector<int> b;
    for (int i = 0; i < l; i++) {
        b.emplace_back(a[i]);
    }
    sort(b.begin(), b.end());
    bitset<N> x = f(b);
    for (int i = 0; i < n; i++) {
        int res = 0;
        for (int j = 0; j < 8; j++) {
            if (x[i * 8 + j]) {
                res |= 1 << j;
            }
        }
        output(res);
    }
}
#endif

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

decoder

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#define decoder

const int N = 600;

void add(bitset<N>& a, const bitset<N>& b) {
    int c = 0;
    for (int i = 0; i < N; i++) {
        int nc = (a[i] & b[i]) | (b[i] & c) | (c & a[i]);
        if (b[i] ^ c) {
            a[i].flip();
        }
        c = nc;
    }
}

bitset<N> f(const vector<int>& b) {
    vector<bitset<N>> dp(256);
    for (int i = 0; i < b[0]; i++) {
        dp[i] = bitset<N>(1);
    }
    for (int i = 0; i < (int) b.size(); i++) {
        vector<bitset<N>> new_dp(256);
        for (int j = 0; j < 256; j++) {
            for (int k = j; k < 256; k++) {
                add(new_dp[k], dp[j]);
            }
        }
        for (int j = b[i]; j < 256; j++) {
            add(new_dp[j], bitset<N>(1));
        }
        swap(dp, new_dp);
    }
    bitset<N> res;
    for (int i = 0; i < 256; i++) {
        add(res, dp[i]);
    }
    return res;
}

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

void encode(int n, int a[]) {
    bitset<N> x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 8; j++) {
            if (a[i] & (1 << j)) {
                x[i * 8 + j].flip();
            }
        }
    }
    vector<int> b(n * 5);
    for (int i = 0; i < n * 5; i++) {
        int low = 0;
        int high = 256;
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            b[i] = mid;
            bitset<N> y = f(b);
            y.flip();
            add(y, x);
            if (y[N - 1]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        b[i] = low;
    }
    for (int i = 0; i < n * 5; i++) {
        send(b[i]);
    }
    assert(f(b) == x);
}
#endif

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

void decode(int n, int l, int a[]) {
    vector<int> b;
    for (int i = 0; i < l; i++) {
        b.emplace_back(a[i]);
    }
    sort(b.begin(), b.end());
    bitset<N> x = f(b);
    for (int i = 0; i < n; i++) {
        int res = 0;
        for (int j = 0; j < 8; j++) {
            if (x[i * 8 + j]) {
                res |= 1 << j;
            }
        }
        output(res);
    }
}
#endif

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

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