oj.uz

Submission #979082

# Submission time Handle Problem Language Result Execution time Memory
979082 2024-05-10T07:58:30 Z sunnat Permutation (APIO22_perm) C++17
100 / 100
 2 ms 604 KB 
#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 --;
        }
    }
    return a;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct