Submission #684856

#	Time	Username	Problem	Language	Result	Execution time	Memory
684856		happypotato	Permutation (APIO22_perm)	C++17	0 / 100	1 ms	212 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, take, notake;
void recur(long long k) {
    if (k <= 4) {
        if (k == 2) ans = {0};
        if (k == 3) ans = {multi++, 0};
        if (k == 4) ans = {0, multi++};
        return;
    }
    if (k & 1) {
        recur((k - 1) / 2);
        ans.push_back(multi++);
        ans.push_back(notake--);
    } else {
        recur((k - 2) / 2);
        ans.push_back(multi++);
        ans.push_back(take--);
    }
}
vector<int> construct_permutation(long long k) {
    ans.clear();
    multi = 1000;
    take = 999;
    notake = -1;
    recur(k);
    discretise(ans);
    return ans;
}

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