Submission #518503

#	Time	Username	Problem	Language	Result	Execution time	Memory
518503		tabr	Parrots (IOI11_parrots)	C++17	17 / 100	24 ms	1176 KiB

encoder

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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

long long f(long long n, int c) {  // count x <= n, popcount(x) == c
    vector<long long> dp(c + 1);
    int d = 0;
    for (int i = 40; i >= 0; i--) {
        for (int j = c - 1; j >= 0; j--) {
            dp[j + 1] += dp[j];
        }
        if (n & (1LL << i)) {
            if (d <= c) {
                dp[d]++;
            }
            d++;
        }
    }
    if (__builtin_popcountll(n) == c) {
        dp[c]++;
    }
    return dp[c];
}

#ifdef encoder
void encode(int n, int a[]) {
    for (int beg = 0; beg < n; beg += 4) {
        int c = min(4, n - beg);
        long long z = 0;
        for (int i = beg; i < min(n, beg + 4); i++) {
            z *= 256;
            z += a[i];
        }
        long long low = -1;
        long long high = 1LL << 40;
        while (high - low > 1) {
            long long mid = (high + low) >> 1;
            if (f(mid, c * 5) >= z + 1) {
                high = mid;
            } else {
                low = mid;
            }
        }
        long long k = high;
        vector<int> b;
        int lst = 0;
        for (int i = 0; i < c * 5 + 16; i++) {
            if (k & (1LL << i)) {
                b.emplace_back(lst);
            } else {
                lst++;
            }
        }
        if (k == 0) {
            for (int i = 0; i < c * 5; i++) {
                b.emplace_back(0);
            }
        }
        for (int i : b) {
            send(i + beg * 4);
        }
    }
}
#endif

#ifdef decoder
void decode(int n, int l, int a[]) {
    sort(a, a + l);
    for (int beg = 0; beg < n; beg += 4) {
        int c = min(4, n - beg);
        vector<int> b;
        for (int i = beg * 5; i < min(n, beg + 4) * 5; i++) {
            b.emplace_back(a[i] - beg * 4);
        }
        long long k = 0;
        for (int i = 0; i < (int) b.size(); i++) {
            k |= 1 << (i + b[i]);
        }
        long long z = f(k, c * 5) - 1;
        b.clear();
        for (int i = 0; i < c; i++) {
            b.emplace_back((int) (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

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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

long long f(long long n, int c) {  // count x <= n, popcount(x) == c
    vector<long long> dp(c + 1);
    int d = 0;
    for (int i = 40; i >= 0; i--) {
        for (int j = c - 1; j >= 0; j--) {
            dp[j + 1] += dp[j];
        }
        if (n & (1LL << i)) {
            if (d <= c) {
                dp[d]++;
            }
            d++;
        }
    }
    if (__builtin_popcountll(n) == c) {
        dp[c]++;
    }
    return dp[c];
}

#ifdef encoder
void encode(int n, int a[]) {
    for (int beg = 0; beg < n; beg += 4) {
        int c = min(4, n - beg);
        long long z = 0;
        for (int i = beg; i < min(n, beg + 4); i++) {
            z *= 256;
            z += a[i];
        }
        long long low = -1;
        long long high = 1LL << 40;
        while (high - low > 1) {
            long long mid = (high + low) >> 1;
            if (f(mid, c * 5) >= z + 1) {
                high = mid;
            } else {
                low = mid;
            }
        }
        long long k = high;
        vector<int> b;
        int lst = 0;
        for (int i = 0; i < c * 5 + 16; i++) {
            if (k & (1LL << i)) {
                b.emplace_back(lst);
            } else {
                lst++;
            }
        }
        if (k == 0) {
            for (int i = 0; i < c * 5; i++) {
                b.emplace_back(0);
            }
        }
        for (int i : b) {
            send(i + beg * 4);
        }
    }
}
#endif

#ifdef decoder
void decode(int n, int l, int a[]) {
    sort(a, a + l);
    for (int beg = 0; beg < n; beg += 4) {
        int c = min(4, n - beg);
        vector<int> b;
        for (int i = beg * 5; i < min(n, beg + 4) * 5; i++) {
            b.emplace_back(a[i] - beg * 4);
        }
        long long k = 0;
        for (int i = 0; i < (int) b.size(); i++) {
            k |= 1 << (i + b[i]);
        }
        long long z = f(k, c * 5) - 1;
        b.clear();
        for (int i = 0; i < c; i++) {
            b.emplace_back((int) (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: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 29
• Subtask 5: 0 / 19