competitive-programming-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kmyk/competitive-programming-library

:warning: old/factoradic.inc.cpp

Back to top page

Code

template <class RandomAccessIterator>
uint64_t encode_factoradic(RandomAccessIterator first, RandomAccessIterator last) { // O(N^2)
    static vector<int> fact(1, 1);
    while (fact.size() < n) {
        fact.push_back(fact.size() * fact.back());
    }
    int n = last - first;
    uint64_t y = 0;
    REP (i, n) {
        int xi = *(first + i);
        int rank = count_if(first, first + i, [&](int xj) { return xi < xj; });
        y += rank * fact[i];
    }
    return y;
}
vector<int> decode_factoradic(uint64_t y, int n) { // O(N^2)
    static vector<int> fact(1, 1);
    while (fact.size() < n) {
        fact.push_back(fact.size() * fact.back());
    }
    vector<int> xs(n);
    vector<int> zs(n); iota(zs.begin(), zs.end(), 0);
    REP_R (i, n) {
        auto it = zs.begin() + (i - y / fact[i]);
        xs[i] = *it;
        zs.erase(it);
        y %= fact[i];
    }
    return xs;
}

#line 1 "old/factoradic.inc.cpp"
template <class RandomAccessIterator>
uint64_t encode_factoradic(RandomAccessIterator first, RandomAccessIterator last) { // O(N^2)
    static vector<int> fact(1, 1);
    while (fact.size() < n) {
        fact.push_back(fact.size() * fact.back());
    }
    int n = last - first;
    uint64_t y = 0;
    REP (i, n) {
        int xi = *(first + i);
        int rank = count_if(first, first + i, [&](int xj) { return xi < xj; });
        y += rank * fact[i];
    }
    return y;
}
vector<int> decode_factoradic(uint64_t y, int n) { // O(N^2)
    static vector<int> fact(1, 1);
    while (fact.size() < n) {
        fact.push_back(fact.size() * fact.back());
    }
    vector<int> xs(n);
    vector<int> zs(n); iota(zs.begin(), zs.end(), 0);
    REP_R (i, n) {
        auto it = zs.begin() + (i - y / fact[i]);
        xs[i] = *it;
        zs.erase(it);
        y %= fact[i];
    }
    return xs;
}

Back to top page