oj.uz

답안 #578341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578341 2022-06-16T11:57:45 Z johnf 순열 (APIO22_perm) C++17
81.1077 / 100
 408 ms 1132 KB 
#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 = 70;
    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) {
            debug(cnt);
            break;
        }
    }
    ll need = k - cnt;
    auto tmp = construct1(need);
    for (auto &x : ans) {
        x += tmp.size();
    }
    ans.insert(ans.end(), all(tmp));
    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 'vi sub2::construct2(ll)':
perm.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
perm.cpp:126:13: note: in expansion of macro 'debug'
  126 |             debug(cnt);
      |             ^~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
71.107692309 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 324 KB Output is correct
4 Correct 69 ms 308 KB Output is correct
5 Partially correct 305 ms 488 KB Partially correct
6 Correct 225 ms 420 KB Output is correct
7 Partially correct 408 ms 588 KB Partially correct
8 Partially correct 370 ms 956 KB Partially correct
9 Correct 146 ms 288 KB Output is correct
10 Partially correct 350 ms 1132 KB Partially correct
11 Partially correct 402 ms 928 KB Partially correct
12 Partially correct 329 ms 752 KB Partially correct
13 Partially correct 404 ms 704 KB Partially correct