Submission #1201791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201791		adiyer	Permutation (APIO22_perm)	C++20	100 / 100	2 ms	328 KiB

perm

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(ll k, int b, bool f, vector < int > &a){
    if(b <= 0) return;
    b -= 2;
    if(b == -1){
        a.push_back(a.size());
        if(k & 1){
            for(int &x : a) x++;
            a.push_back(0);
        }
        return;
    }
    int t = (k >> b) & 3;
    if(a.empty()){
        if(t == 2) a = {0};
        else a = {1, 0}, f = 1;
    }
    else{
        if(t == 0){
            a.push_back(a.size());
            a.push_back(a.size());
        }
        else if(t == 1){
            a.push_back(a.size());
            a.push_back(a.size());
            for(int &x : a) x++;
            a.push_back(0), f = 1;
        }
        else if(t == 2){
            a.push_back(a.size());
            for(int &x : a) x++;
            a.push_back(0);
            a.push_back(a.size()), f = 1;
        }
        else if(f){
            a.push_back(a.size());
            a.push_back(a.size());
            for(int &x : a)
                if(x > 1)
                    x++;
            a.push_back(2);
        }
        else{
            a.push_back(a.size());
            for(int &x : a) x++;
            a.push_back(0);
            a.push_back(a.size());
            for(int &x : a) x++;
            a.push_back(0);
            f = 1;
        }
    }
    solve(k, b, f, a);
}

vector < int > a;

vector < int > construct_permutation(ll k){
    a.clear(), solve(k, 64 - __builtin_clzll(k), 0, a);
    return a;
}

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