Submission #760595

#	Time	Username	Problem	Language	Result	Execution time	Memory
760595		coding_snorlax	Permutation (APIO22_perm)	C++17	71.22 / 100	11 ms	1320 KiB

perm

#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
//Main function split it to #(2^k-1)
int cal_log2(long long int k){
    int ans = 0;
    while(k>>=1) ++ans;
    return ans;
}
long long int cal_pow(int a){
    long long int ans = 1;
    while(a){
        ans*=2;
        a-=1;
    }
    return ans;
}

vector<int> split(long long int k){
    vector<int> ans;
    while(k){
        //cout << k << " ";
        long long int a = cal_log2(k+1);
        ans.push_back(a);
        k -= (long long int) cal_pow(a)-1;
    }
    return  ans;
}

vector<int> construct_permutation(long long int k)
{
    k-=1;
    vector<int> process = split(k);
    int Count = 0;
    for(int i:process){
        Count+=i;
    }
    vector<int> s;
    for(int i:process){
        for(int j=Count-i;j<Count;j++){
            s.push_back(j);
        }
        Count-=i;
    }
	return s;
}
/*
int main(){

    //vector<int> answer = construct_permutation(3);
    //for(int i:answer) cout << i << " ";
    vector<int> answer = construct_permutation(100);//split((long long int)1024*1024*1024*1024*1024*1024-1);
    for(int i:answer) cout << i << " ";
}
*/

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