Submission #518499

#	Time	Username	Problem	Language	Result	Execution time	Memory
518499		tabr	Parrots (IOI11_parrots)	C++17	81 / 100	1222 ms	133232 KiB

encoder

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

#define encoder

#ifdef tabr
int dat[100];
int id = 0;
void send(int x) {
    dat[id++] = x;
}
void output(int x) {
    cout << x << '\n';
}
#else
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#endif

int w1[1 << 8];
int w2[1 << 16];
int w3[1 << 24];

int* w[4];

int ids[4];

void build() {
    for (int i = 0; i < (1 << 27); i++) {
        if (ids[3] == (1 << 24)) {
            break;
        }
        int c = __builtin_popcount(i);
        if (c == 5 && ids[1] < (1 << 8)) {
            w1[ids[1]++] = i;
        }
        if (c == 10 && ids[2] < (1 << 16)) {
            w2[ids[2]++] = i;
        }
        if (c == 15 && ids[3] < (1 << 24)) {
            w3[ids[3]++] = i;
        }
    }
    w[1] = w1;
    w[2] = w2;
    w[3] = w3;
}

#ifdef encoder
void encode(int n, int a[]) {
    build();
    for (int beg = 0; beg < n; beg += 3) {
        int c = min(3, n - beg);
        int z = 0;
        for (int i = beg; i < min(n, beg + 3); i++) {
            z *= 256;
            z += a[i];
        }
        int k = w[c][z];
        vector<int> b;
        int lst = 0;
        for (int i = 0; i < c * 5 + 12; i++) {
            if (k & (1 << i)) {
                b.emplace_back(lst);
            } else {
                lst++;
            }
        }
        for (int i : b) {
            send(i + beg * 4);
        }
    }
}
#endif

#ifdef decoder
void decode(int n, int l, int a[]) {
    build();
    sort(a, a + l);
    for (int beg = 0; beg < n; beg += 3) {
        int c = min(3, n - beg);
        vector<int> b;
        for (int i = beg * 5; i < min(n, beg + 3) * 5; i++) {
            b.emplace_back(a[i] - beg * 4);
        }
        int k = 0;
        for (int i = 0; i < (int) b.size(); i++) {
            k |= 1 << (i + b[i]);
        }
        int z = (int) (lower_bound(w[c], w[c] + ids[c], k) - w[c]);
        b.clear();
        for (int i = 0; i < c; i++) {
            b.emplace_back(z % 256);
            z /= 256;
        }
        reverse(b.begin(), b.end());
        for (int i : b) {
            output(i);
        }
    }
}
#endif

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 6;
    int a[] = {1, 1, 4, 5, 1, 4};
    encode(n, a);
    decode(n, id, dat);
    return 0;
}
#endif

decoder

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

#define decoder

#ifdef tabr
int dat[100];
int id = 0;
void send(int x) {
    dat[id++] = x;
}
void output(int x) {
    cout << x << '\n';
}
#else
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#endif

int w1[1 << 8];
int w2[1 << 16];
int w3[1 << 24];

int* w[4];

int ids[4];

void build() {
    for (int i = 0; i < (1 << 27); i++) {
        if (ids[3] == (1 << 24)) {
            break;
        }
        int c = __builtin_popcount(i);
        if (c == 5 && ids[1] < (1 << 8)) {
            w1[ids[1]++] = i;
        }
        if (c == 10 && ids[2] < (1 << 16)) {
            w2[ids[2]++] = i;
        }
        if (c == 15 && ids[3] < (1 << 24)) {
            w3[ids[3]++] = i;
        }
    }
    w[1] = w1;
    w[2] = w2;
    w[3] = w3;
}

#ifdef encoder
void encode(int n, int a[]) {
    build();
    for (int beg = 0; beg < n; beg += 3) {
        int c = min(3, n - beg);
        int z = 0;
        for (int i = beg; i < min(n, beg + 3); i++) {
            z *= 256;
            z += a[i];
        }
        int k = w[c][z];
        vector<int> b;
        int lst = 0;
        for (int i = 0; i < c * 5 + 12; i++) {
            if (k & (1 << i)) {
                b.emplace_back(lst);
            } else {
                lst++;
            }
        }
        for (int i : b) {
            send(i + beg * 4);
        }
    }
}
#endif

#ifdef decoder
void decode(int n, int l, int a[]) {
    build();
    sort(a, a + l);
    for (int beg = 0; beg < n; beg += 3) {
        int c = min(3, n - beg);
        vector<int> b;
        for (int i = beg * 5; i < min(n, beg + 3) * 5; i++) {
            b.emplace_back(a[i] - beg * 4);
        }
        int k = 0;
        for (int i = 0; i < (int) b.size(); i++) {
            k |= 1 << (i + b[i]);
        }
        int z = (int) (lower_bound(w[c], w[c] + ids[c], k) - w[c]);
        b.clear();
        for (int i = 0; i < c; i++) {
            b.emplace_back(z % 256);
            z /= 256;
        }
        reverse(b.begin(), b.end());
        for (int i : b) {
            output(i);
        }
    }
}
#endif

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 6;
    int a[] = {1, 1, 4, 5, 1, 4};
    encode(n, a);
    decode(n, id, dat);
    return 0;
}
#endif

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