Submission #707695

#	Time	Username	Problem	Language	Result	Execution time	Memory
707695		Nhoksocqt1	Parrots (IOI11_parrots)	C++17	100 / 100	583 ms	23628 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
 
#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
 
struct Bignum {
    static const int MAX_DIGIT = 20;
    static const int BASE = (int) 1e9;
    int digits[MAX_DIGIT], numDigit;
 
    Bignum(ll x = 0) {
        numDigit = 0;
        memset(digits, 0, sizeof digits);
 
        if (!x) numDigit = 1;
 
        while (x > 0) {
            digits[numDigit++] = x % BASE;
            x /= BASE;
        }
    }
 
    Bignum(string s) {
        numDigit = 0;
        memset(digits, 0, sizeof digits);
 
        ll x(0);
        int i(s.length() - 1), l(i + 1);
        for (int i = l - 1; i >= 8; i -= 9) {
            digits[numDigit++] = stoll(s.substr(i - 8, 9));
        }
 
        if(l % 9) {
            digits[numDigit++] = stoll(s.substr(0, l % 9));
        }
    }
 
    Bignum& operator += (const Bignum &x) {
        int carry(0);
        numDigit = max(numDigit, x.numDigit);
 
        for (int i = 0; i < numDigit; ++i) {
            digits[i] += x.digits[i] + carry;
 
            if (digits[i] >= BASE) {
                digits[i] -= BASE;
                carry = 1;
            } else {
                carry = 0;
            }
        }
 
        if (carry)
            digits[numDigit++] = carry;
 
        return *this;
    }
 
    Bignum operator + (const Bignum &x) const {
        Bignum res(*this);
        return res += x;
    }
 
    Bignum& operator -= (const Bignum &x) {
        int carry(0);
        for (int i = 0; i < numDigit; ++i) {
            digits[i] -= x.digits[i] + carry;
            if (digits[i] < 0) {
                digits[i] += BASE;
                carry = 1;
            } else carry = 0;
        }
 
        while (numDigit > 1 && !digits[numDigit - 1]) --numDigit;
 
        return *this;
    }
 
    Bignum operator - (const Bignum &x) const {
        Bignum res(*this);
        res -= x;
        return res;
    }
 
    Bignum& operator *= (int x) {
        if (!x) {
            *this = Bignum(0);
            return *this;
        }
 
        ll remain = 0;
        for (int i = 0; i < numDigit; ++i) {
            remain += 1LL * digits[i] * x;
            digits[i] = remain % BASE;
            remain /= BASE;
        }
 
        while (remain > 0) {
            digits[numDigit++] = remain % BASE;
            remain /= BASE;
        }
 
        return *this;
    }
 
    Bignum operator * (int x) const {
        Bignum res(*this);
        res *= x;
        return res;
    }
 
    ll operator % (ll x) const {
		ll res(0);
		for (int i = numDigit - 1; i >= 0; i--)
            res = (res * BASE + digits[i]) % x;
 
		return res;
	}
 
	Bignum operator / (ll x) const {
		Bignum res(0);
		ll rem(0);
		for (int i = numDigit - 1; i >= 0; i--) {
			res.digits[i] = (BASE * rem + digits[i]) / x;
			rem = (BASE * rem + digits[i]) % x;
		}
 
		res.numDigit = numDigit;
		while (res.numDigit > 1 && !res.digits[res.numDigit - 1]) --res.numDigit;
		return res;
	}
 
    #define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))
    int compare(const Bignum &x) const {
        if (numDigit != x.numDigit) {
            return COMPARE(numDigit, x.numDigit);
        }
 
        for (int i = numDigit - 1; i >= 0; --i) {
            if (digits[i] != x.digits[i]) {
                return COMPARE(digits[i], x.digits[i]);
            }
        }
        return 0;
    }
 
    #define DEF_OPER(o) bool operator o (const Bignum &x) const { return compare(x) o 0; }
    DEF_OPER(<) DEF_OPER(>) DEF_OPER(>=) DEF_OPER(<=) DEF_OPER(==) DEF_OPER(!=)
    #undef DEF_OPER
 
    string toString(void) const {
        string res;
        for (int i = 0; i < numDigit; ++i) {
            int tmp = digits[i];
            for (int j = 0; j < 9; ++j) {
                res.push_back('0' + tmp % 10);
                tmp /= 10;
            }
        }
 
        while (res.size() > 1 && res.back() == '0') {
            res.pop_back();
        }
 
        reverse(res.begin(), res.end());
        return res;
    }
 
} C[260][520];
 
void encode(int N, int M[]) {
    Bignum 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] = C[i][j - 1] + C[i - 1][j - 1];
    }
 
    for (int i = 0; i < N * 8; ++i)
        X += X;
 
    for (int i = N; ; ++i) {
        if(C[256][256 + i - 1] >= X) {
            K = i;
            break;
        }
    }
 
    //cout << X.toString() << ' ' << C[256][256 + K - 1].toString() << '\n';
    for (int i = 0; i < N; ++i)
        num = num * 256 + M[i];
 
    //cout << num.toString() << '\n';
    num += 1;
 
    int last(0);
    for (int i = 0; i < K; ++i) {
        for (int val = last; val < 256; ++val) {
            Bignum &way = C[255 - val][255 - val + K - i - 1];
            //cout << i << ' ' << val << ' ' << num.toString() << ' ' << way.toString() << '\n';
            if(num <= way) {
                last = val;
                send(val);
                break;
            }
 
            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] = C[i][j - 1] + C[i - 1][j - 1];
    }
 
    //cout << "Time run: " << clock() - time << " ms.\n";
    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) {
        if(token[it] != m[it]) {
            cout << '.';
        }
 
        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);
}
 
#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
 
struct Bignum {
    static const int MAX_DIGIT = 20;
    static const int BASE = (int) 1e9;
    int digits[MAX_DIGIT], numDigit;
 
    Bignum(ll x = 0) {
        numDigit = 0;
        memset(digits, 0, sizeof digits);
 
        if (!x) numDigit = 1;
 
        while (x > 0) {
            digits[numDigit++] = x % BASE;
            x /= BASE;
        }
    }
 
    Bignum(string s) {
        numDigit = 0;
        memset(digits, 0, sizeof digits);
 
        ll x(0);
        int i(s.length() - 1), l(i + 1);
        for (int i = l - 1; i >= 8; i -= 9) {
            digits[numDigit++] = stoll(s.substr(i - 8, 9));
        }
 
        if(l % 9) {
            digits[numDigit++] = stoll(s.substr(0, l % 9));
        }
    }
 
    Bignum& operator += (const Bignum &x) {
        int carry(0);
        numDigit = max(numDigit, x.numDigit);
 
        for (int i = 0; i < numDigit; ++i) {
            digits[i] += x.digits[i] + carry;
 
            if (digits[i] >= BASE) {
                digits[i] -= BASE;
                carry = 1;
            } else {
                carry = 0;
            }
        }
 
        if (carry)
            digits[numDigit++] = carry;
 
        return *this;
    }
 
    Bignum operator + (const Bignum &x) const {
        Bignum res(*this);
        return res += x;
    }
 
    Bignum& operator -= (const Bignum &x) {
        int carry(0);
        for (int i = 0; i < numDigit; ++i) {
            digits[i] -= x.digits[i] + carry;
            if (digits[i] < 0) {
                digits[i] += BASE;
                carry = 1;
            } else carry = 0;
        }
 
        while (numDigit > 1 && !digits[numDigit - 1]) --numDigit;
 
        return *this;
    }
 
    Bignum operator - (const Bignum &x) const {
        Bignum res(*this);
        res -= x;
        return res;
    }
 
    Bignum& operator *= (int x) {
        if (!x) {
            *this = Bignum(0);
            return *this;
        }
 
        ll remain = 0;
        for (int i = 0; i < numDigit; ++i) {
            remain += 1LL * digits[i] * x;
            digits[i] = remain % BASE;
            remain /= BASE;
        }
 
        while (remain > 0) {
            digits[numDigit++] = remain % BASE;
            remain /= BASE;
        }
 
        return *this;
    }
 
    Bignum operator * (int x) const {
        Bignum res(*this);
        res *= x;
        return res;
    }
 
    ll operator % (ll x) const {
		ll res(0);
		for (int i = numDigit - 1; i >= 0; i--)
            res = (res * BASE + digits[i]) % x;
 
		return res;
	}
 
	Bignum operator / (ll x) const {
		Bignum res(0);
		ll rem(0);
		for (int i = numDigit - 1; i >= 0; i--) {
			res.digits[i] = (BASE * rem + digits[i]) / x;
			rem = (BASE * rem + digits[i]) % x;
		}
 
		res.numDigit = numDigit;
		while (res.numDigit > 1 && !res.digits[res.numDigit - 1]) --res.numDigit;
		return res;
	}
 
    #define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))
    int compare(const Bignum &x) const {
        if (numDigit != x.numDigit) {
            return COMPARE(numDigit, x.numDigit);
        }
 
        for (int i = numDigit - 1; i >= 0; --i) {
            if (digits[i] != x.digits[i]) {
                return COMPARE(digits[i], x.digits[i]);
            }
        }
        return 0;
    }
 
    #define DEF_OPER(o) bool operator o (const Bignum &x) const { return compare(x) o 0; }
    DEF_OPER(<) DEF_OPER(>) DEF_OPER(>=) DEF_OPER(<=) DEF_OPER(==) DEF_OPER(!=)
    #undef DEF_OPER
 
    string toString(void) const {
        string res;
        for (int i = 0; i < numDigit; ++i) {
            int tmp = digits[i];
            for (int j = 0; j < 9; ++j) {
                res.push_back('0' + tmp % 10);
                tmp /= 10;
            }
        }
 
        while (res.size() > 1 && res.back() == '0') {
            res.pop_back();
        }
 
        reverse(res.begin(), res.end());
        return res;
    }
 
} C[260][520];
 
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] = C[i][j - 1] + C[i - 1][j - 1];
    }
 
    Bignum num(0);
    for (int i = 0; i < L; ++i) {
        for (int j = (i == 0 ? 0 : X[i - 1]); j < X[i]; ++j) {
            num += C[255 - j][255 - j + L - i - 1];
        }
    }
 
    stack<int> st;
    while(num > 0) {
        st.push(num % 256);
        num = 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] = C[i][j - 1] + C[i - 1][j - 1];
    }
 
    //cout << "Time run: " << clock() - time << " ms.\n";
    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) {
        if(token[it] != m[it]) {
            cout << '.';
        }
 
        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")
      | 
encoder.cpp: In constructor 'Bignum::Bignum(std::string)':
encoder.cpp:64:12: warning: unused variable 'x' [-Wunused-variable]
   64 |         ll x(0);
      |            ^

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 constructor 'Bignum::Bignum(std::string)':
decoder.cpp:62:12: warning: unused variable 'x' [-Wunused-variable]
   62 |         ll x(0);
      |            ^
decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:231:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  231 |     while(st.size() < N)
      |           ~~~~~~~~~~^~~

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