Submission #394467

#	Time	Username	Problem	Language	Result	Execution time	Memory
394467		MarcoMeijer	Parrots (IOI11_parrots)	C++14	100 / 100	283 ms	61452 KiB

encoder

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = 80;

struct BigNumb {
    int v[MX];
    BigNumb() {
        RE(i,MX) v[i] = 0;
    }
    BigNumb(int x) {
        RE(i,MX) v[i] = 0;
        v[0] = x;
        update();
    }
    BigNumb operator+(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        RE(i,MX) result.v[i] += rhs.v[i];
        result.update();
        return result;
    }
    BigNumb operator-(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        REV(i,1,MX) {
            result.v[i] -= rhs.v[i];
            if(result.v[i]) {
                result.v[i]--;
                result.v[i-1] += 256;
            }
        }
        result.v[0] -= rhs.v[0];
        result.update();
        return result;
    }
    BigNumb& operator+=(const BigNumb& rhs) {*this = (*this)+rhs; return *this;}
    BigNumb& operator-=(const BigNumb& rhs) {*this = (*this)-rhs; return *this;}
    BigNumb& operator=(int rhs) {*this = BigNumb(rhs); return *this;}
    bool operator>=(const BigNumb& rhs) const {
        REV(i,0,MX) if(v[i] != rhs.v[i]) return v[i] > rhs.v[i];
        return true;
    }
    void update() {
        RE(i,MX-1) while(v[i] >= 256) v[i] -= 256, v[i+1]++;
    }
};

BigNumb ways[350][270];

void fillWays() {
    RE(i,270) ways[0][i] = i+1;
    REP(i,1,350) RE(j,270) {
        if(j) ways[i][j] += ways[i][j-1];
        ways[i][j] += ways[i-1][j];
    }
}
BigNumb getWays(int dif, int len) {
    if(dif == 0) return BigNumb(0);
    return ways[len-1][dif-1];
}
vll encode(BigNumb x, int mx, int len) {
    if(len == 0) return {};
    RE1(i,mx) {
        if(getWays(i,len) >= x) {
            vll res = encode(x - getWays(i-1,len), i, len-1);
            res.pb(i);
            return res;
        }
    }
    return {};
}

void encode(int N, int M[]) {
    static bool first = true;
    if(first) {
        fillWays();
        first = false;
    }

    BigNumb x;
    RE(i,N) x.v[i] = M[i];
    x += BigNumb(1);
    vll res = encode(x, 256, N*5);
    FOR(i,res) send(i-1);
}

decoder

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = 80;

struct BigNumb {
    int v[MX];
    BigNumb() {
        RE(i,MX) v[i] = 0;
    }
    BigNumb(int x) {
        RE(i,MX) v[i] = 0;
        v[0] = x;
        update();
    }
    BigNumb operator+(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        RE(i,MX) result.v[i] += rhs.v[i];
        result.update();
        return result;
    }
    BigNumb operator-(const BigNumb& rhs) const {
        BigNumb result;
        result = *this;
        REV(i,1,MX) {
            result.v[i] -= rhs.v[i];
            if(result.v[i]) {
                result.v[i]--;
                result.v[i-1] += 256;
            }
        }
        result.v[0] -= rhs.v[0];
        result.update();
        return result;
    }
    BigNumb& operator+=(const BigNumb& rhs) {*this = (*this)+rhs; return *this;}
    BigNumb& operator-=(const BigNumb& rhs) {*this = (*this)-rhs; return *this;}
    BigNumb& operator=(int rhs) {*this = BigNumb(rhs); return *this;}
    bool operator>=(const BigNumb& rhs) const {
        REV(i,0,MX) if(v[i] != rhs.v[i]) return v[i] > rhs.v[i];
        return true;
    }
    void update() {
        RE(i,MX-1) while(v[i] >= 256) v[i] -= 256, v[i+1]++;
    }
};

BigNumb ways[350][270];

void fillWays() {
    RE(i,270) ways[0][i] = i+1;
    REP(i,1,350) RE(j,270) {
        if(j) ways[i][j] += ways[i][j-1];
        ways[i][j] += ways[i-1][j];
    }
}
BigNumb getWays(int dif, int len) {
    if(dif == 0) return BigNumb(0);
    return ways[len-1][dif-1];
}
vll encode(BigNumb x, int mx, int len) {
    if(len == 0) return {};
    RE1(i,mx) {
        if(getWays(i,len) >= x) {
            vll res = encode(x - getWays(i-1,len), i, len-1);
            res.pb(i);
            return res;
        }
    }
    return {};
}
BigNumb decode(vll v) {
    if(v.empty()) return 1;
    int last = v.back();
    v.pop_back();
    BigNumb res = decode(v);
    res += getWays(last-1, v.size()+1);
    return res;
}

void decode(int N, int L, int X[]) {
    static bool first = true;
    if(first) {
        fillWays();
        first = false;
    }
    
    vll v;
    RE(i,L) v.pb(X[i]+1);
    sort(all(v));
    BigNumb res = decode(v);
    res -= BigNumb(1);
    RE(i,N) output(res.v[i]);
}

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