Submission #577380

#	Time	Username	Problem	Language	Result	Execution time	Memory
577380		jeroenodb	Parrots (IOI11_parrots)	C++14	100 / 100	109 ms	21184 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace encoding {
    #define all(x) begin(x),end(x)
    template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
    template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
    #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
    typedef vector<int> vi;
    typedef pair<int,int> pi;

    const int B = 256;
    const int Base=B*B;
    
    struct bigint {
        vi v = {0};
        int size() const {return v.size();}
        void trim() {
            int carry=0;
            for(int i=0;i<size();++i) {
                v[i]+=carry;
                carry = v[i]/Base;
                v[i]%=Base;
            }
            while(carry) {
                v.push_back(carry%Base);
                carry/=Base;
            }
            while(!v.empty() and v.back()==0) v.pop_back();
        }
        bigint() {}
        bigint(int a) {
            v = {a};
            trim();
        }
        bigint(int n, int A[]) { // in base B
            v= {};
            for(int i=0;i<n;i+=2) {
                v.push_back(A[i]);
                if(i+1<n) v.back()+=A[i+1]*B;
            }
            trim();
        }
        bigint& operator+=(const bigint& o) {
            if(o.size()>size()) {
                v.resize(o.size());
            }
            for(int i=0;i<o.size();++i) {
                v[i]+=o.v[i];
            }
            trim();
            return *this;
        }
        bool operator>(const bigint& o) const {
            if(size()>o.size()) return true;
            if(size()<o.size()) return false;
            for(int i=size()-1;i>=0;--i) {
                if(v[i]>o.v[i]) return true;
                if(v[i]<o.v[i]) return false;
            }
            return false;
        }
        bool operator>=(const bigint& o) const {
            if(v==o.v) return true;
            return *this>o;
        }

        bigint operator+(bigint o) {
            o+=*this;
            return o;
        }
        vi digs() {
            vi res;
            for(auto i : v) {
                for(int j=0;j<2;++j) {
                    res.push_back(i%B);
                    i/=B;
                }
            }
            return res;
        }
    };
    struct NCR {
        map<pi,bigint> mp;
        bigint ncr(int n, int k) {
            if(k<0 or k>n) return {0};
            if(k==0 or k==n) return {1};
            if(mp.count({n,k})) return mp[{n,k}];
            auto& tmp =  mp[{n,k}] = ncr(n-1,k-1)+ncr(n-1,k);
            return tmp;
        }
        bigint paths(int n, int m) {
            return ncr(n+m,m);
        }
    };
}

static encoding::NCR c;
void encode(int N, int M[]) {
    using namespace encoding;
    bigint used = 0;
    bigint total(N,M);
    int L=0;
    while(true) {
        bigint tmp = c.paths(L,B-1);
        if(total>=used+tmp) {
            used+=tmp;
        } else break;
        ++L;
    }
    vi res;
    int at=0;
    while(res.size()!=L) {
        int left = L-res.size();
        bigint tmp = c.paths(left-1,B-1-at);
        auto nxt = tmp+used;
        if(nxt>total) {
            res.push_back(at);
        } else {
            used=nxt;
            ++at;
        }
    }
    for(auto& i : res) send(i);

}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include "bits/stdc++.h"
using namespace std;
namespace decoding {
    #define all(x) begin(x),end(x)
    template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
    template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
    #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
    typedef vector<int> vi;
    typedef pair<int,int> pi;

    const int B = 256;
    const int Base=B*B;
    
    struct bigint {
        vi v = {0};
        int size() const {return v.size();}
        void trim() {
            int carry=0;
            for(int i=0;i<size();++i) {
                v[i]+=carry;
                carry = v[i]/Base;
                v[i]%=Base;
            }
            while(carry) {
                v.push_back(carry%Base);
                carry/=Base;
            }
            while(!v.empty() and v.back()==0) v.pop_back();
        }
        bigint() {}
        bigint(int a) {
            v = {a};
            trim();
        }
        bigint(int n, int A[]) { // in base B
            for(int i=0;i<n;i+=2) {
                v.push_back(A[i]);
                if(i+1<n) v.back()+=A[i+1]*B;
            }
            trim();
        }
        bigint& operator+=(const bigint& o) {
            if(o.size()>size()) {
                v.resize(o.size());
            }
            for(int i=0;i<o.size();++i) {
                v[i]+=o.v[i];
            }
            trim();
            return *this;
        }
        bool operator>(const bigint& o) const {
            if(size()>o.size()) return true;
            if(size()<o.size()) return false;
            for(int i=size()-1;i>=0;--i) {
                if(v[i]>o.v[i]) return true;
                if(v[i]<o.v[i]) return false;
            }
            return false;
        }
        bool operator>=(const bigint& o) const {
            if(v==o.v) return true;
            return *this>o;
        }

        bigint operator+(bigint o) {
            o+=*this;
            return o;
        }
        vi digs() {
            vi res;
            for(auto i : v) {
                for(int j=0;j<2;++j) {
                    res.push_back(i%B);
                    i/=B;
                }
            }
            return res;
        }
    };
    struct NCR {
        map<pi,bigint> mp;
        bigint ncr(int n, int k) {
            if(k<0 or k>n) return {0};
            if(k==0 or k==n) return {1};
            if(mp.count({n,k})) return mp[{n,k}];
            auto& tmp =  mp[{n,k}] = ncr(n-1,k-1)+ncr(n-1,k);
            return tmp;
        }
        bigint paths(int n, int m) {
            return ncr(n+m,m);
        }
    };
}

static decoding::NCR c;
void decode(int N, int L, int X[]) {
    using namespace decoding;
    sort(X,X+L);
    bigint res = 0;
    for(int i=0;i<L;++i) {
        res+=c.paths(i,B-1);
    }
    int last=0;
    for(int i=0;i<L;++i) {
        int cur = X[i];
        while(last<cur) {
            int goright = L-i-1;
            res+=c.paths(goright,B-1-last);
            ++last;
        }
    }
    auto digs = res.digs();
    digs.resize(N);
    for(auto i : digs) output(i);
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:114:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |     while(res.size()!=L) {
      |           ~~~~~~~~~~^~~

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