oj.uz

답안 #577380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577380 2022-06-14T16:24:21 Z jeroenodb 앵무새 (IOI11_parrots) C++14
100 / 100
 109 ms 21184 KB 
#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);

}

#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

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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1408 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1792 KB Output is correct
2 Correct 9 ms 2060 KB Output is correct
3 Correct 12 ms 2660 KB Output is correct
4 Correct 13 ms 2704 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1796 KB Output is correct
2 Correct 9 ms 2060 KB Output is correct
3 Correct 11 ms 2568 KB Output is correct
4 Correct 12 ms 2640 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1800 KB Output is correct
2 Correct 11 ms 2692 KB Output is correct
3 Correct 17 ms 3564 KB Output is correct
4 Correct 25 ms 5532 KB Output is correct
5 Correct 27 ms 5852 KB Output is correct
6 Correct 33 ms 6168 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 2776 KB Output is correct - P = 1.750000
2 Correct 28 ms 6168 KB Output is correct - P = 2.437500
3 Correct 31 ms 6308 KB Output is correct - P = 2.484848
4 Correct 62 ms 12920 KB Output is correct - P = 3.280000
5 Correct 95 ms 18704 KB Output is correct - P = 3.833333
6 Correct 104 ms 20464 KB Output is correct - P = 4.015873
7 Correct 109 ms 21184 KB Output is correct - P = 4.078125