Submission #1208061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208061		fskarica	Permutation (APIO22_perm)	C++20	91.33 / 100	1 ms	328 KiB

perm

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

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

vector <int> construct_permutation(long long k) {
    vector <int> ret;

    int firstBit;
    for (ll i = 60; i >= 0; i--) {
        if ((1ll << i) & k) {
            firstBit = i;
            break;
        }
    }

    vector <int> v;
    for (int i = firstBit - 1; i >= 0; i--) {
        if ((1ll << i) & k) {
            v.push_back(0);
            v.push_back(1);
        }
        else {
            v.push_back(0);
        }
    }
    reverse(v.begin(), v.end());

    for (auto e : v) ret.push_back(0);

    int numb = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == 0) {
            ret[i] = numb;
            numb++;
        }
    }

    for (int i = v.size() - 1; i >= 0; i--) {
        if (v[i] == 1) {
            ret[i] = numb;
            numb++;
        }
    }

    return ret;
}

//int countWays(vector <int> v) {
//    vector <int> dp;
//    for (auto e : v) dp.push_back(0);
//
//    dp[0] = 0;
//    for (int i = 0; i < v.size(); i++) {
//        dp[i] = 1;
//
//        for (int j = i - 1; j >= 0; j--) {
//            if (v[i] > v[j]) {
//                dp[i] = dp[j] * 2;
//                break;
//            }
//        }
//    }
//
//    int ret = 1;
//    for (auto e : dp) ret += e;
//
//    return ret;
//}
//
//int main() {
//    int t;
//
//    cin >> t;
//    while (t--) {
//        int x; cin >> x;
//        for (auto e : construct_permutation(x)) cout << e << " "; cout << " - sol\n";
//        cout << countWays(construct_permutation(x)) << "\n";
//        cout << "\n";
//    }
//
//    return 0;
//}

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