Submission #578376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578376	2022-06-16T13:16:27 Z	johnf	Permutation (APIO22_perm)	C++17	89.4923 / 100	836 ms	1052 KB

perm

#include "perm.h"
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using vi = vector<int>;

template <class T>
bool uin(T &a, T b) {
    return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

template <class T, class Apply>
struct FenwickTree {
    const T identity;
    std::vector<T> f;
    const Apply apply;
    FenwickTree(int n, const T identity_, const Apply &apply_)
        : identity(identity_), f(n + 1, identity_), apply(apply_) {}
    void init(int n) { f.assign(n + 1, identity); }
    void update(int x, T d) {
        for (; x < (int)f.size(); x += x & -x) {
            apply(f[x], d);
        }
    }
    T prefix(int x) const {
        T ans(identity);
        for (; x > 0; x &= x - 1) {
            apply(ans, f[x]);
        }
        return ans;
    }
};
template <class T, class Apply>
FenwickTree<T, Apply> makeFenwickTree(int n, const T identity, const Apply &apply) {
    return FenwickTree<T, Apply>(n, identity, apply);
}

namespace sub1 {
bool eligible(ll k) { return k <= 90; }
vi construct_permutation(ll k) {
    vi ans;
    ford(i, k - 1) { ans.pb(i); }
    return ans;
}
}

namespace sub2 {
bool eligible(ll k) { return 1; }
vi construct1(ll k) {
    vi vec;
    for (int i = 62; i; i--) {
        while (k >= (1LL << i) - 1) {
            k -= (1LL << i) - 1;
            vec.pb(i);
        }
    }
    int n = accumulate(all(vec), 0);
    vi ans;
    for (auto d : vec) {
        fore(i, n - d, n - 1) { ans.pb(i); }
        n -= d;
    }
    return ans;
}
ll cal(vi vec) {
    int n = vec.size();
    auto f = makeFenwickTree<ll>(n, 0, [](ll &x, ll y) { x += y; });
    ll ans = 0;
    for0(i, n) {
        ll dp = f.prefix(vec[i] + 1) + 1;
        f.update(vec[i] + 1, dp);
        ans += dp;
        if (ans > (ll)1e18) {
            return (ll)1e18 + 1;
        }
    }
    return ans;
}
vi construct2_util(ll k) {
    int n = 63 - __builtin_clzll(k) + 20;
    if (k < n) {
        return construct1(k);
    }
    vi ans;
    ford(i, n) { ans.pb(i); }
    ll cnt = cal(ans);
    while (cnt < k) {
        bool found = 0;
        for0(i, n - 1) {
            if (ans[i] < ans[i + 1]) {
                continue;
            }
            swap(ans[i], ans[i + 1]);
            ll cur = cal(ans);
            if (cur > cnt && cur <= k) {
                cnt = cur;
                found = 1;
                break;
            }
            swap(ans[i], ans[i + 1]);
        }
        if (!found) {
            break;
        }
    }
    return ans;
}
vi construct2(ll k) {
    vi ans;
    while (k) {
        auto cur = construct2_util(k);
        ll cnt = cal(cur);
        k -= cnt;
        for (auto &x : ans) {
            x += cur.size();
        }
        ans.insert(ans.end(), all(cur));
    }
    return ans;
}
vi construct_permutation(ll k) {
    k--;
    auto ans = construct1(k);
    auto cur = construct2(k);
    if (ans.size() > cur.size()) {
        ans = cur;
    }
    return ans;
}
}

std::vector<int> construct_permutation(long long k) {
    if (sub1::eligible(k)) {
        return sub1::construct_permutation(k);
    }
    if (sub2::eligible(k)) {
        return sub2::construct_permutation(k);
    }
}

Compilation message

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:165:1: warning: control reaches end of non-void function [-Wreturn-type]
  165 | }
      | ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	228 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct

Subtask #2

79.492307688 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	228 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	13 ms	320 KB	Output is correct
4	Correct	47 ms	308 KB	Output is correct
5	Partially correct	350 ms	460 KB	Partially correct
6	Correct	188 ms	496 KB	Output is correct
7	Partially correct	454 ms	620 KB	Partially correct
8	Partially correct	752 ms	1052 KB	Partially correct
9	Correct	230 ms	432 KB	Output is correct
10	Partially correct	836 ms	936 KB	Partially correct
11	Partially correct	705 ms	712 KB	Partially correct
12	Partially correct	583 ms	876 KB	Partially correct
13	Partially correct	768 ms	628 KB	Partially correct