oj.uz

답안 #613600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613600 2022-07-30T07:20:14 Z Aldas25 순열 (APIO22_perm) C++17
91.3333 / 100
 3 ms 340 KB 
#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.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Partially correct 2 ms 340 KB Partially correct
6 Correct 2 ms 300 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Partially correct 3 ms 340 KB Partially correct
9 Correct 1 ms 340 KB Output is correct
10 Partially correct 3 ms 340 KB Partially correct
11 Partially correct 2 ms 300 KB Partially correct
12 Partially correct 1 ms 340 KB Partially correct
13 Partially correct 2 ms 340 KB Partially correct