Submission #578337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578337	2022-06-16T11:52:10 Z	johnf	Permutation (APIO22_perm)	C++17	72.8615 / 100	800 ms	1132 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 = 90;
    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() < 800) {
        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

62.861538465 / 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	26 ms	448 KB	Output is correct
4	Correct	81 ms	280 KB	Output is correct
5	Partially correct	612 ms	560 KB	Partially correct
6	Correct	271 ms	436 KB	Output is correct
7	Correct	542 ms	620 KB	Output is correct
8	Partially correct	798 ms	784 KB	Partially correct
9	Correct	371 ms	412 KB	Output is correct
10	Partially correct	792 ms	1132 KB	Partially correct
11	Partially correct	793 ms	792 KB	Partially correct
12	Partially correct	741 ms	668 KB	Partially correct
13	Partially correct	800 ms	664 KB	Partially correct