oj.uz

Submission #249719

# Submission time Handle Problem Language Result Execution time Memory
249719 2020-07-15T15:24:04 Z eohomegrownapps Parrots (IOI11_parrots) C++14
100 / 100
 1662 ms 2288 KB 
#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;
            }
        }
    }
}
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 940 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1536 KB Output is correct
2 Correct 69 ms 1512 KB Output is correct
3 Correct 117 ms 1520 KB Output is correct
4 Correct 137 ms 1816 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1536 KB Output is correct
2 Correct 67 ms 1464 KB Output is correct
3 Correct 118 ms 1520 KB Output is correct
4 Correct 144 ms 1520 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1536 KB Output is correct
2 Correct 140 ms 1520 KB Output is correct
3 Correct 186 ms 1520 KB Output is correct
4 Correct 383 ms 1528 KB Output is correct
5 Correct 407 ms 1520 KB Output is correct
6 Correct 431 ms 1520 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1520 KB Output is correct - P = 5.000000
2 Correct 434 ms 1608 KB Output is correct - P = 5.000000
3 Correct 456 ms 1520 KB Output is correct - P = 5.000000
4 Correct 1036 ms 2288 KB Output is correct - P = 5.000000
5 Correct 1473 ms 2024 KB Output is correct - P = 5.000000
6 Correct 1621 ms 2032 KB Output is correct - P = 5.000000
7 Correct 1662 ms 2032 KB Output is correct - P = 5.000000