Submission #979082

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
979082	2024-05-10 07:58:30	sunnat	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	604 KiB

perm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;
vector<int> construct_permutation(long long k){
    vector<int> a;
    while((1ll<<a.size()) <= k) a.push_back(a.size());
    a.pop_back();
    k -= 1LL<<a.size();
    if(k > 0){
        int bt = 60;
        while(!((k >> bt)&1)) --bt;
        for(int &x:a) if(x >= bt) ++ x;
        a.push_back(bt);
        k -= 1LL<<bt --;
        while(bt >= 0){
            if(bt > 0 && (k>>(bt-1)) == 3){
                --bt;
                for(int &x:a) if(x >= bt) ++ x;
                a.insert(a.end() - 2, bt);
                k -= 3LL<<bt--;
            }
            else if((k >> bt) == 1){
                for(int &x:a) if(x >= bt) ++x;
                a.push_back(bt);
                k -= 1LL<<bt--;
            }
            else bt --;
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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