Submission #578368

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578368	2022-06-16T13:07:15 Z	johnf	Permutation (APIO22_perm)	C++17	89.4769 / 100	930 ms	980 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 = 77;
    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	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct

Subtask #2

79.476923079 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	36 ms	316 KB	Output is correct
4	Correct	104 ms	292 KB	Output is correct
5	Partially correct	518 ms	420 KB	Partially correct
6	Correct	299 ms	504 KB	Output is correct
7	Partially correct	549 ms	608 KB	Partially correct
8	Partially correct	764 ms	700 KB	Partially correct
9	Correct	227 ms	308 KB	Output is correct
10	Partially correct	894 ms	980 KB	Partially correct
11	Partially correct	728 ms	668 KB	Partially correct
12	Partially correct	658 ms	692 KB	Partially correct
13	Partially correct	930 ms	728 KB	Partially correct