Submission #707683

#	Time	Username	Problem	Language	Result	Execution time	Memory
707683		Nhoksocqt1	Parrots (IOI11_parrots)	C++17	17 / 100	2076 ms	33288 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

//#define Nhoksocqt1

string C[260][520];
#ifdef Nhoksocqt1

vector<int> encoder, token;

void send(int a) {
    assert(a >= 0 && a <= 255);
    encoder.push_back(a);
}

void output(int b) {
    token.push_back(b);
}

#endif // Nhoksocqt1

string add(const string &a, const string &b) {
    string c;

    int aLen(sz(a)), bLen(sz(b)), len = min(aLen, bLen), rem(0);
    for (int i = len - 1; i >= 0; --i) {
        int div = a[aLen - len + i] + b[bLen - len + i] - 2 * '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    for (int i = 1; aLen - len - i >= 0; ++i) {
        int div = a[aLen - len - i] - '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    for (int i = 1; bLen - len - i >= 0; ++i) {
        int div = b[bLen - len - i] - '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    if(rem > 0)
        c.push_back(rem + '0');

    reverse(c.begin(), c.end());
    return c;
}

string sub(string a, string b) {
    string c;
    int len = max(sz(a), sz(b));
    if(len > sz(a))
        a.insert(0, len - sz(a), '0');

    if(len > sz(b))
        b.insert(0, len - sz(b), '0');

    int rem(0);
    for (int i = len - 1; i >= 0; --i) {
        int div = a[i] - b[i] - rem;
        c.push_back((div + 10) % 10 + '0');
        rem = (div < 0);
    }

    while(c.size() > 1 && c.back() == '0')
        c.pop_back();

    reverse(c.begin(), c.end());
    return c;
}

string mul(const string &a, int k) {
    string res;
    int aLen(sz(a));
    for (int i = 0; i < aLen; ++i) {
        if(res.size())
            res.push_back('0');

        res = add(res, to_string((a[i] - '0') * k));
    }

    return res;
}

string div(const string &a, int k) {
    string res;
    int aLen(sz(a)), rem(0);
    for (int i = 0; i < aLen; ++i) {
        rem = rem * 10 + a[i] - '0';
        if(res.size() || rem >= k)
            res.push_back(rem / k + '0');

        rem %= k;
    }

    if(res.empty())
        res.push_back('0');

    return res;
}

int mod(const string &a, int k) {
    string res;
    int aLen(sz(a)), rem(0);
    for (int i = 0; i < aLen; ++i)
        rem = (rem * 10 + a[i] - '0') % k;

    return rem;
}

int Compare(const string &a, const string &b) {
    if(sz(a) != sz(b))
        return (sz(a) > sz(b)) ? 1 : -1;

    for (int i = 0; i < sz(a); ++i) {
        if(a[i] != b[i])
            return (a[i] > b[i]) ? 1 : -1;
    }

    return 0;
}

void encode(int N, int M[]) {
    string X = "1", num = "0";
    int K;

    for (int i = 0; i < 520; ++i)
        C[0][i] = "1";

    for (int i = 1; i <= 256; ++i) {
        C[i][i] = "1";
        for (int j = i + 1; j < 520; ++j)
            C[i][j] = add(C[i][j - 1], C[i - 1][j - 1]);
    }

    for (int i = 0; i < N * 8; ++i)
        X = add(X, X);

    for (int i = N; ; ++i) {
        if(Compare(C[256][256 + i - 1], X) >= 0) {
            K = i;
            break;
        }
    }

    //cout << X << ' ' << C[256][256 + K - 1] << '\n';
    for (int i = 0; i < N; ++i) {
        num = mul(num, 256);
        num = add(num, to_string(M[i]));
    }

    //cout << num << '\n';
    num = add(num, "1");

    int last(0);
    for (int i = 0; i < K; ++i) {
        for (int val = last; val < 256; ++val) {
            string &way = C[256 - val][256 - val + K - i - 1];
            //cout << i << ' ' << val << ' ' << way << ' ' << 256 - val - K + i + 1 << '\n';
            if(Compare(num, way) <= 0) {
                last = val;
                send(val);
                break;
            }

            num = sub(num, way);
        }
    }
}

#ifdef Nhoksocqt1
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("PARROTS.inp", "r", stdin);
    freopen("PARROTS.out", "w", stdout);

    encoder.clear(), token.clear();

    clock_t time = clock();

    for (int i = 0; i < 520; ++i)
        C[0][i] = "1";

    for (int i = 1; i <= 256; ++i) {
        C[i][i] = "1";
        for (int j = i + 1; j < 520; ++j)
            C[i][j] = add(C[i][j - 1], C[i - 1][j - 1]);
    }

    int m[70], L[500], n;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> m[i];
        //m[i] = Random(0, 255); cout << m[i] << " \n"[i + 1 == n];
    }

    encode(n, m);
    cout << "NUMBER BIRD: " << sz(encoder) << '\n';

    for (int it = 0; it < sz(encoder); ++it)
        L[it] = encoder[it];

    shuffle(L, L + sz(encoder), rng);
    decode(n, sz(encoder), L);

    cout << "TOKEN GET: " << sz(token) << '\n';

    assert(sz(token) == n);
    //for (int it = 0; it < n; ++it)
    //    cout << token[it] << " \n"[it + 1 == n];
    for (int it = 0; it < n; ++it)
        assert(token[it] == m[it]);

    return 0;
}
#endif // Nhoksocqt1

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

//#define Nhoksocqt1

string C[260][520];
#ifdef Nhoksocqt1

vector<int> encoder, token;

void send(int a) {
    assert(a >= 0 && a <= 255);
    encoder.push_back(a);
}

void output(int b) {
    token.push_back(b);
}

#endif // Nhoksocqt1

string add(const string &a, const string &b) {
    string c;

    int aLen(sz(a)), bLen(sz(b)), len = min(aLen, bLen), rem(0);
    for (int i = len - 1; i >= 0; --i) {
        int div = a[aLen - len + i] + b[bLen - len + i] - 2 * '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    for (int i = 1; aLen - len - i >= 0; ++i) {
        int div = a[aLen - len - i] - '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    for (int i = 1; bLen - len - i >= 0; ++i) {
        int div = b[bLen - len - i] - '0' + rem;
        c.push_back(div % 10 + '0');
        rem = div / 10;
    }

    if(rem > 0)
        c.push_back(rem + '0');

    reverse(c.begin(), c.end());
    return c;
}

string sub(string a, string b) {
    string c;
    int len = max(sz(a), sz(b));
    if(len > sz(a))
        a.insert(0, len - sz(a), '0');

    if(len > sz(b))
        b.insert(0, len - sz(b), '0');

    int rem(0);
    for (int i = len - 1; i >= 0; --i) {
        int div = a[i] - b[i] - rem;
        c.push_back((div + 10) % 10 + '0');
        rem = (div < 0);
    }

    while(c.size() > 1 && c.back() == '0')
        c.pop_back();

    reverse(c.begin(), c.end());
    return c;
}

string mul(const string &a, int k) {
    string res;
    int aLen(sz(a));
    for (int i = 0; i < aLen; ++i) {
        if(res.size())
            res.push_back('0');

        res = add(res, to_string((a[i] - '0') * k));
    }

    return res;
}

string div(const string &a, int k) {
    string res;
    int aLen(sz(a)), rem(0);
    for (int i = 0; i < aLen; ++i) {
        rem = rem * 10 + a[i] - '0';
        if(res.size() || rem >= k)
            res.push_back(rem / k + '0');

        rem %= k;
    }

    if(res.empty())
        res.push_back('0');

    return res;
}

int mod(const string &a, int k) {
    string res;
    int aLen(sz(a)), rem(0);
    for (int i = 0; i < aLen; ++i)
        rem = (rem * 10 + a[i] - '0') % k;

    return rem;
}

int Compare(const string &a, const string &b) {
    if(sz(a) != sz(b))
        return (sz(a) > sz(b)) ? 1 : -1;

    for (int i = 0; i < sz(a); ++i) {
        if(a[i] != b[i])
            return (a[i] > b[i]) ? 1 : -1;
    }

    return 0;
}

void decode(int N, int L, int X[]) {
    sort(X, X + L);

    for (int i = 0; i < 520; ++i)
        C[0][i] = "1";

    for (int i = 1; i <= 256; ++i) {
        C[i][i] = "1";
        for (int j = i + 1; j < 520; ++j)
            C[i][j] = add(C[i][j - 1], C[i - 1][j - 1]);
    }

    string num("0");
    for (int i = 0; i < L; ++i) {
        for (int j = (i == 0 ? 0 : X[i - 1]); j < X[i]; ++j) {
            num = add(num, C[256 - j][256 - j + L - i - 1]);
        }
    }

    stack<int> st;
    while(Compare(num, "0") > 0) {
        st.push(mod(num, 256));
        num = div(num, 256);
    }

    while(st.size() < N)
        st.push(0);

    while(st.size()) {
        output(st.top());
        st.pop();
    }
}

#ifdef Nhoksocqt1
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("PARROTS.inp", "r", stdin);
    freopen("PARROTS.out", "w", stdout);

    encoder.clear(), token.clear();

    clock_t time = clock();

    for (int i = 0; i < 520; ++i)
        C[0][i] = "1";

    for (int i = 1; i <= 256; ++i) {
        C[i][i] = "1";
        for (int j = i + 1; j < 520; ++j)
            C[i][j] = add(C[i][j - 1], C[i - 1][j - 1]);
    }

    int m[70], L[500], n;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> m[i];
        //m[i] = Random(0, 255); cout << m[i] << " \n"[i + 1 == n];
    }

    encode(n, m);
    cout << "NUMBER BIRD: " << sz(encoder) << '\n';

    for (int it = 0; it < sz(encoder); ++it)
        L[it] = encoder[it];

    shuffle(L, L + sz(encoder), rng);
    decode(n, sz(encoder), L);

    cout << "TOKEN GET: " << sz(token) << '\n';

    assert(sz(token) == n);
    //for (int it = 0; it < n; ++it)
    //    cout << token[it] << " \n"[it + 1 == n];
    for (int it = 0; it < n; ++it)
        assert(token[it] == m[it]);

    return 0;
}
#endif // Nhoksocqt1

Compilation message (stderr)

encoder.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
encoder.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 

decoder.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
decoder.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:172:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  172 |     while(st.size() < N)
      |           ~~~~~~~~~~^~~

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