Submission #578340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578340	2022-06-16T11:55:23 Z	johnf	Permutation (APIO22_perm)	C++17	74.2154 / 100	199 ms	1340 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(ll k) {
    int n = 60;
    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;
        }
    }
    ll need = k - cnt;
    auto tmp = construct1(need);
    for (auto &x : ans) {
        x += tmp.size();
    }
    ans.insert(ans.end(), all(tmp));
    return ans;
}
auto init_time = chrono::high_resolution_clock::now();
vi construct_permutation(ll k) {
    k--;
    auto ans = construct1(k);
    auto current_time = chrono::high_resolution_clock::now();
    if (chrono::duration<double, milli>(current_time - init_time).count() < 950) {
        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:159:1: warning: control reaches end of non-void function [-Wreturn-type]
  159 | }
      | ^

Subtask #1

10.0 / 10.0

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

Subtask #2

64.215384615 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	17 ms	344 KB	Output is correct
4	Correct	55 ms	296 KB	Output is correct
5	Partially correct	138 ms	452 KB	Partially correct
6	Correct	187 ms	444 KB	Output is correct
7	Partially correct	199 ms	780 KB	Partially correct
8	Partially correct	138 ms	972 KB	Partially correct
9	Correct	100 ms	308 KB	Output is correct
10	Partially correct	113 ms	1340 KB	Partially correct
11	Partially correct	145 ms	852 KB	Partially correct
12	Partially correct	159 ms	856 KB	Partially correct
13	Partially correct	134 ms	844 KB	Partially correct