Submission #613600

#	Time	Username	Problem	Language	Result	Execution time	Memory
613600		Aldas25	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	340 KiB

perm

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

using namespace std;

#define pb push_back
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAXN = 500100;

vi getPow (ll k) {
    vi ret;
    /*while (k) {

        ll i =0;
        while ((1ll<<(i+1))-1 <= k) {
            i++;
        }

        ret.pb(i);
        k -= (1ll<<i)-1;

    }*/

    FOR(i, 0, 60) {
        if ((1ll<<i) & k) {
            ret.pb(i);
        }
    }
    return ret;
}

void printSeq (vi seq) {
    cout << " seq: ";
    for (int x : seq)cout << x << " ";
    cout << endl;
}

std::vector<int> construct_permutation(long long k)
{
    //k--; /// empty subseqence

    vi ret;
    vi powers = getPow (k);

    vi a;
    vii b;
    int sz = powers.size();
    FOR(i, 0, powers[sz-1]-1) a.pb(i);
    k -= (1ll<<(powers[sz-1]));

    for (int i = powers[sz-1]-1; i >= 0; i--) {
        if (k < (1ll<<i)) continue;
        int z = 0;
        for (; z <= 60; z++) {
            ll cr = (1ll<<i) * ((1ll<<z)-1);
            if (cr > k) break;
        }
        z--;
        ll cr = (1ll<<i) * ((1ll<<z)-1);
        k -= cr;
        b.pb({i, z});
        //cout << "  in b i = " << i << " z = " << z << endl;
    }

    reverse(b.begin(), b.end());

    //FOR(i, 0, sz-2) b.pb(powers[i]);

    int aid = 0, bid = 0;

    //int sum = (int)a.size() + (int)b.size();
    int sum = (int)a.size();
    for (auto p : b) sum += p.s;

    while (aid < (int)a.size() || bid < (int)b.size()) {
        if (aid >= (int)a.size() || (bid < (int)b.size() && b[bid].f == a[aid])) {
            int fr = sum-b[bid].s, to = sum-1;
            FOR(xx, fr, to) ret.pb(xx);
            bid++;
            sum = fr;
        } else {
            ret.pb(a[aid]);
            aid++;
        }
    }

   // printSeq(ret);

	return ret;
}

/*

2
3
8

*/

• Subtask 1: 10 / 10
• Subtask 2: 81.333333333 / 90