Submission #575484

#	Time	Username	Problem	Language	Result	Execution time	Memory
575484		MadokaMagicaFan	Parrots (IOI11_parrots)	C++14	100 / 100	51 ms	22552 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 64;
const int A = 256;

void send(int a);
void output(int a);

struct bignum {
    vector<ll> vals;
    ll sz = (1l<<32);

    bignum() {vals.pb(0);}
    bignum(ll i) {vals.pb(i);}
    bignum(const bignum& x) { equal(x); }

    int
    comp(const bignum& x)
    {
        int ind1;
        int ind2;

        for (ind2 = sz(x.vals)-1; ind2 >= 0; --ind2) {
            if (x.vals[ind2])
                break;
        }

        for (ind1 = sz(vals)-1; ind1 >= 0; --ind1) {
            if (vals[ind1])
                break;
        }

        if (ind1 > ind2)
            return 1;
        if (ind1 < ind2)
            return -1;

        while (ind1 > -1) {
            if (vals[ind1] > x.vals[ind1])
                return 1;
            if (vals[ind1] < x.vals[ind1])
                return -1;
            --ind1;
        }

        return 0;
    }

    void
    equal(const bignum& x)
    {
        vals.clear();
        for (int i = 0; i < sz(x.vals); ++i)
            vals.pb(x.vals[i]);
        return;
    }

    void
    setval(int pos, ll val)
    {
        int blk = pos/4;
        while (sz(vals) <= blk)
            vals.pb(0);
        pos %= 4;
        vals[blk] += (val<<(pos*8));

        assert(vals[blk] < sz);
    }

    int
    getval(int pos)
    {
        ll ans;
        int blk = pos/4;
        if (sz(vals) <= blk)
            return 0;
        pos %= 4;
        ans = vals[blk]>>(pos*8);
        ans %= A;
        return ans;
    }

    void
    add(const bignum& x)
    {
        ll reminder = 0;
        int ind = 0;
        while (ind < sz(x.vals) || reminder) {
            if (ind >= sz(vals))
                vals.pb(0);
            vals[ind] += reminder;
            if (ind < sz(x.vals))
                vals[ind] += x.vals[ind];
            reminder = vals[ind]/sz;
            vals[ind] %= sz;
            ++ind;
        }
        return;
    }

    void
    add(ll x)
    {
        ll reminder = x;
        int ind = 0;
        while (reminder) {
            if (ind >= sz(vals))
                vals.pb(0);
            vals[ind] += reminder;
            reminder = vals[ind]/sz;
            vals[ind] %= sz;
            ++ind;
        }
        return;
    }
    
    void
    subtr(const bignum& x)
    {
        assert(this->comp(x) > -1);

        ll reminder = 0;
        int ind = 0;
        while (ind < sz(x.vals) || reminder) {
            if (ind >= sz(vals))
                assert(0);
            vals[ind] -= reminder;
            if (ind < sz(x.vals))
                vals[ind] -= x.vals[ind];
            if (vals[ind] < 0) {
                reminder = 0;
                while (vals[ind] < 0) {
                    vals[ind] += sz;
                    ++reminder;
                }
            } else {
                reminder = 0;
            }
            ++ind;
        }
        return;
    }

    void
    subtr()
    {
        for (int i = 0; i < sz(vals); ++i) {
            if (vals[i]) {
                vals[i] -= 1;
                break;
            }
            vals[i] = sz-1;
        }
        return;
    }

    void
    print()
    {
        for (int i = sz(vals)-1; i >= 0; --i) {
            cout << i << ": " << vals[i] << endl;
        }
        return;
    }
};

bignum dp[5*N][A];


void
init()
{
    if (dp[0][1].comp(1)==0)
        return;
    for (int i = 0; i < A; ++i) {
        if(i) {
            dp[0][i].equal(dp[0][i-1]);
            dp[0][i].add(1);
        }
    }

    for (int i = 1; i < 5*N; ++i) {
        for (int j = 0; j < A; ++j) {
            if (j)
                dp[i][j].equal(dp[i][j-1]);
            dp[i][j].add(dp[i-1][j]);
        }
    }

    return;
}

void
encode(int n, int *m)
{
    init();

    bignum value(0);
    for (int i = 0; i < n; ++i) {
        value.setval(i,m[i]);
    }

    if (value.comp(0) == 0) {
        send(69);
        return;
    }

    int lb=A-1;

    for (int i = n*5-1; i >= 0; --i) {
        for (int j = lb; j >= 0; --j) {
            if (value.comp(0) == 0)
                send(0);
            if (value.comp(dp[i][j]) > 0) {
                assert(j < A-1);
                value.subtr(dp[i][j]);
                send(j+1);
                lb = j+1;
                break;
            } else if (!j)
                assert(0);
        }
    }
    return;
}
#ifdef ONPC
int _a[5*N];
int _m[N];
int _l = 0;

void
send(int a)
{
    _a[_l] = a;
    ++_l;
}
void output(int a)
{
    cout << a << ' ';
}

void
solve()
{
    int _n;
    cin >> _n;
    for (int i = 0; i < _n; ++i)
        cin >> _m[i];

    encode(_n,_m);
    cout << _n << endl;
    decode(_n,_l,_a);
    cout << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

decoder

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

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 64;
const int A = 256;

void send(int a);
void output(int a);

struct bignum {
    vector<ll> vals;
    ll sz = (1l<<32);

    bignum() {vals.pb(0);}
    bignum(ll i) {vals.pb(i);}
    bignum(const bignum& x) { equal(x); }

    int
    comp(const bignum& x)
    {
        int ind1;
        int ind2;

        for (ind2 = sz(x.vals)-1; ind2 >= 0; --ind2) {
            if (x.vals[ind2])
                break;
        }

        for (ind1 = sz(vals)-1; ind1 >= 0; --ind1) {
            if (vals[ind1])
                break;
        }

        if (ind1 > ind2)
            return 1;
        if (ind1 < ind2)
            return -1;

        while (ind1 > -1) {
            if (vals[ind1] > x.vals[ind1])
                return 1;
            if (vals[ind1] < x.vals[ind1])
                return -1;
            --ind1;
        }

        return 0;
    }

    void
    equal(const bignum& x)
    {
        vals.clear();
        for (int i = 0; i < sz(x.vals); ++i)
            vals.pb(x.vals[i]);
        return;
    }

    void
    setval(int pos, ll val)
    {
        int blk = pos/4;
        while (sz(vals) <= blk)
            vals.pb(0);
        pos %= 4;
        vals[blk] += (val<<(pos*8));

        assert(vals[blk] < sz);
    }

    int
    getval(int pos)
    {
        ll ans;
        int blk = pos/4;
        if (sz(vals) <= blk)
            return 0;
        pos %= 4;
        ans = vals[blk]>>(pos*8);
        ans %= A;
        return ans;
    }

    void
    add(const bignum& x)
    {
        ll reminder = 0;
        int ind = 0;
        while (ind < sz(x.vals) || reminder) {
            if (ind >= sz(vals))
                vals.pb(0);
            vals[ind] += reminder;
            if (ind < sz(x.vals))
                vals[ind] += x.vals[ind];
            reminder = vals[ind]/sz;
            vals[ind] %= sz;
            ++ind;
        }
        return;
    }

    void
    add(ll x)
    {
        ll reminder = x;
        int ind = 0;
        while (reminder) {
            if (ind >= sz(vals))
                vals.pb(0);
            vals[ind] += reminder;
            reminder = vals[ind]/sz;
            vals[ind] %= sz;
            ++ind;
        }
        return;
    }
    
    void
    subtr(const bignum& x)
    {
        assert(this->comp(x) > -1);

        ll reminder = 0;
        int ind = 0;
        while (ind < sz(x.vals) || reminder) {
            if (ind >= sz(vals))
                assert(0);
            vals[ind] -= reminder;
            if (ind < sz(x.vals))
                vals[ind] -= x.vals[ind];
            if (vals[ind] < 0) {
                reminder = 0;
                while (vals[ind] < 0) {
                    vals[ind] += sz;
                    ++reminder;
                }
            } else {
                reminder = 0;
            }
            ++ind;
        }
        return;
    }

    void
    subtr()
    {
        for (int i = 0; i < sz(vals); ++i) {
            if (vals[i]) {
                vals[i] -= 1;
                break;
            }
            vals[i] = sz-1;
        }
        return;
    }

    void
    print()
    {
        for (int i = sz(vals)-1; i >= 0; --i) {
            cout << i << ": " << vals[i] << endl;
        }
        return;
    }
};

bignum dp[5*N][A];


void
init()
{
    if (dp[0][1].comp(1)==0)
        return;
    for (int i = 0; i < A; ++i) {
        if(i) {
            dp[0][i].equal(dp[0][i-1]);
            dp[0][i].add(1);
        }
    }

    for (int i = 1; i < 5*N; ++i) {
        for (int j = 0; j < A; ++j) {
            if (j)
                dp[i][j].equal(dp[i][j-1]);
            dp[i][j].add(dp[i-1][j]);
        }
    }

    return;
}

void
decode(int n, int l, int *k)
{
    if (l == 1) {
        for (int i = 0; i < n; ++i) output(0);
        return;
    }

    init();

    assert(l == 5*n);
    bignum val(1);

    vector<int> s;

    for (int i = 0; i < l; ++i) {
        s.pb(k[i]);
    }

    sort(s.begin(), s.end());

    for (int i = sz(s)-1; i >= 0; --i) {
        if (s[i] == 0)
            break;
        val.add(dp[i][s[i]-1]);
    }

    for (int i = 0; i < n; ++i) {
        output(val.getval(i));
    }


    return;
}


#ifdef ONPC
int _a[5*N];
int _m[N];
int _l = 0;

void
send(int a)
{
    _a[_l] = a;
    ++_l;
}
void output(int a)
{
    cout << a << ' ';
}

void
solve()
{
    int _n;
    cin >> _n;
    for (int i = 0; i < _n; ++i)
        cin >> _m[i];

    encode(_n,_m);
    cout << _n << endl;
    decode(_n,_l,_a);
    cout << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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