Submission #684889

#	Time	Username	Problem	Language	Result	Execution time	Memory
684889		happypotato	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
void discretise(vector<int> &v) {
    map<int, int> mp;
    for (int i = 0; i < (int)(v.size()); i++) {
        mp[v[i]] = i;
    }
    int cnt = 0;
    for (pair<int, int> cur : mp) {
        v[cur.second] = cnt++;
    }
}
vector<int> ans;
int multi, add, buff;
void recur(long long k) {
    // cerr << "DOING " << k << endl;
    if (k == 2) {
        ans = {0};
        return;
    } else if (k == 3) {
        ans = {0, -1000}; add -= 1000;
        return;
    } else if (k == 7) {
        ans = {-1000, -2000, 0, -3000}; add -= 3000;
        return;
    }

    if (k % 4 == 3) {
        recur(k / 4);
        if (add != -1000) {
            ans.push_back(multi); multi += 1000;
            ans.push_back(multi); multi += 1000;
            ans.push_back(add + 2000 + buff); buff--;
        } else {
            ans.push_back(multi); multi += 1000;
            ans.push_back(add); add -= 1000; buff = 999;
            ans.push_back(multi); multi += 1000;
            ans.push_back(add); add -= 1000; buff = 999;
        }
    } else if (k & 1) {
        recur(k - 1);
        ans.push_back(add); add -= 1000; buff = 999;
    } else {
        recur(k / 2);
        ans.push_back(multi); multi += 1000;
    }
}
void checking(vector<int> &v) {
    int n = v.size();
    long long dp[n];
    long long tot = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                dp[i] += dp[j];
            }
        }
        tot += dp[i];
    }
    cout << "Total number of subsequences is " << tot << endl;
}
vector<int> construct_permutation(long long k) {
    ans.clear();
    multi = 1000;
    add = -1000;
    buff = 999;
    recur(k);
    discretise(ans);
    // cout << "Answer: ";
    // for (int &x : ans) cout << x << ' '; cout << endl;
    // checking(ans);
    return ans;
}

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