Submission #1201795

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

perm

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void add(vector < int > &a, int r){
    for(int &x : a)
        if(x >= r)
            x++;
    a.push_back(r);
}

void solve(ll k, int b, bool f, vector < int > &a){
    b -= 2;
    if(b < -1) return;
    if(b == -1){
        add(a, a.size());
        if(k & 1) add(a, 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) add(a, a.size()), add(a, a.size());
        else if(t == 1) add(a, a.size()), add(a, a.size()), add(a, 0), f = 1;
        else if(t == 2) add(a, a.size()), add(a, 0), add(a, a.size()), f = 1;
        else if(f) add(a, a.size()), add(a, a.size()), add(a, 2);
        else add(a, a.size()), add(a, 0), add(a, a.size()), add(a, 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