Submission #249719

#	Time	Username	Problem	Language	Result	Execution time	Memory
249719		eohomegrownapps	Parrots (IOI11_parrots)	C++14	100 / 100	1662 ms	2288 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

static lll lm = 1e18;

struct Num{
    //11 long longs
    lll vals[11];
    int s = 11;
    Num(ll _val){
        for (int i = 1; i<s; i++){
            vals[i]=0;
        }
        vals[0]=_val;
    }

    bool operator < (Num y) {
        for (int i = s-1; i>=0; i--){
            if (y.vals[i]>vals[i]){
                return true;
            }
            if (y.vals[i]<vals[i]){
                return false;
            }
        }
        return false;
    }

    bool operator > (Num y) {
        return y<(*this);
    }

    bool operator == (Num y){
        for (int i = s-1; i>=0; i--){
            if (y.vals[i]!=vals[i]){
                return false;
            }
        }
        return true;
    }

    Num operator + (Num y){
        lll carry = 0;
        Num ans = Num(0);
        for (int i = 0; i<s; i++){
            lll tot = lll(vals[i])+lll(y.vals[i])+carry;
            carry = tot/lm;
            ans.vals[i] = tot%lm;
        }
        return ans;
    }

    Num operator - (Num y){
        assert(!(y>(*this)));
        Num ans = Num(0);
        for (int i = 0; i<s; i++){
            if (vals[i]<0){
                vals[i]+=lm;
                if (i<s-1){
                    vals[i+1]--;
                } else {
                    assert(1==0);
                }
            }
            lll diff = vals[i]-y.vals[i];
            if (diff>=0){
                ans.vals[i]=diff;
            } else {
                diff+=lm;
                ans.vals[i]=diff;
                if (i<s-1){
                    vals[i+1]--;
                } else {
                    assert(1==0);
                }
            }
        }
        return ans;
    }

    Num operator * (ll y){
        //assume we only have to x by int
        Num ans = Num(0);
        lll carry = 0;
        for (int i = 0; i<s; i++){
            lll cur = vals[i]*y+carry;
            carry=cur/lm;
            ans.vals[i]=cur%lm;
        }
        return ans;
    }

    Num operator / (ll y){
        Num ans = Num(0);
        lll carry = 0;
        for (int i = s-1; i>=0; i--){
            lll div = carry*lm+vals[i];
            lll quot = div/y;
            carry = div%y;
            ans.vals[i]=quot;
        }
        return ans;
    }

    ll operator % (ll y){
        return vals[0]%y;
    }

    void print(){
        for (int i = s-1; i>=0; i--){
            cout<<ll(vals[i])<<" ";
        }cout<<'\n';
    }
};

static Num ncr(int n, int r){
    //cout<<n<<" "<<r<<'\n';
    //w+h-1 choose w
    if (n-r<r){
        r=n-r;
    }
    Num ans = Num(1);
    for (int i = 1; i<=r; i++){
        ans = ans*(n-i+1);
        ans = ans/i;
    }
    return ans;
}

void encode(int N, int M[]){
    //msb first
    int n = N;
    int numbirds = n*5;
    Num val = Num(0);
    for (int i = 0; i<n; i++){
        val=val*256;
        val=val+M[i];
    }
    val=val+1;
    //dp
    int curheight = 0;
    int maxheight = 255;
    for (int width = numbirds; width>0; width--){
        //cout<<width<<" at "<<curheight<<'\n';
        for (int h = curheight; h<=maxheight; h++){
            Num check = ncr(width+maxheight-h-1, width-1);//numPoss(width, maxheight-h+1);
            //check.print();
            //number if we put a bird at height h
            if (!(val>check)){ //if check<=val
                send(h);
                curheight=h;
                break;
            } else {
                val = val - check;
            }
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

static lll lm = 1e18;

struct Num{
    //11 long longs
    lll vals[11];
    int s = 11;
    Num(ll _val){
        for (int i = 1; i<s; i++){
            vals[i]=0;
        }
        vals[0]=_val;
    }

    bool operator < (Num y) {
        for (int i = s-1; i>=0; i--){
            if (y.vals[i]>vals[i]){
                return true;
            }
            if (y.vals[i]<vals[i]){
                return false;
            }
        }
        return false;
    }

    bool operator > (Num y) {
        return y<(*this);
    }

    bool operator == (Num y){
        for (int i = s-1; i>=0; i--){
            if (y.vals[i]!=vals[i]){
                return false;
            }
        }
        return true;
    }

    Num operator + (Num y){
        lll carry = 0;
        Num ans = Num(0);
        for (int i = 0; i<s; i++){
            lll tot = lll(vals[i])+lll(y.vals[i])+carry;
            carry = tot/lm;
            ans.vals[i] = tot%lm;
        }
        return ans;
    }

    Num operator - (Num y){
        assert(!(y>(*this)));
        Num ans = Num(0);
        for (int i = 0; i<s; i++){
            if (vals[i]<0){
                vals[i]+=lm;
                if (i<s-1){
                    vals[i+1]--;
                } else {
                    assert(1==0);
                }
            }
            lll diff = vals[i]-y.vals[i];
            if (diff>=0){
                ans.vals[i]=diff;
            } else {
                diff+=lm;
                ans.vals[i]=diff;
                if (i<s-1){
                    vals[i+1]--;
                } else {
                    assert(1==0);
                }
            }
        }
        return ans;
    }

    Num operator * (ll y){
        //assume we only have to x by int
        Num ans = Num(0);
        lll carry = 0;
        for (int i = 0; i<s; i++){
            lll cur = vals[i]*y+carry;
            carry=cur/lm;
            ans.vals[i]=cur%lm;
        }
        return ans;
    }

    Num operator / (ll y){
        Num ans = Num(0);
        lll carry = 0;
        for (int i = s-1; i>=0; i--){
            lll div = carry*lm+vals[i];
            lll quot = div/y;
            carry = div%y;
            ans.vals[i]=quot;
        }
        return ans;
    }

    ll operator % (ll y){
        return vals[0]%y;
    }

    void print(){
        for (int i = s-1; i>=0; i--){
            cout<<ll(vals[i])<<" ";
        }cout<<'\n';
    }
};

static Num ncr(int n, int r){
    //cout<<n<<" "<<r<<'\n';
    //w+h-1 choose w
    if (n-r<r){
        r=n-r;
    }
    Num ans = Num(1);
    for (int i = 1; i<=r; i++){
        ans = ans*(n-i+1);
        ans = ans/i;
    }
    return ans;
}

void decode(int N, int L, int X[]){
    int n = N;
    int l = L;
    sort(X, X+l);
    Num val = Num(0);

    int curheight = 0;
    int maxheight = 255;
    for (int width = l; width>0; width--){
        //cout<<width<<" at "<<curheight<<'\n';
        for (int h = curheight; h<X[l-width]; h++){
            val = val + ncr(width+maxheight-h-1, width-1);//numPoss(width, maxheight-h+1);
        }
        curheight=X[l-width];
    }
    //val.print();
    vector<int> ans;
    for (int i = 0; i<n; i++){
        ans.push_back(val%256);
        val = val / 256;
    }
    for (int i = n-1; i>=0; i--){
        output(ans[i]);
    }
}

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