Submission #724859

#	Time	Username	Problem	Language	Result	Execution time	Memory
724859		Batorgil952	Permutation (APIO22_perm)	C++17	10 / 100	1073 ms	304 KiB

perm

#include<bits/stdc++.h>
#include "perm.h"

using namespace std;

std::vector<int> construct_permutation(long long k)
{
	long long p=2, s=1, r=0;
	while(k>p){
		p*=2;
		s++;
	}
	s--;
	vector< int > v;
	long long a[100], dp[100];
	while(r==0){
		v.clear();
		a[0]=0;
		for(long long i=0; i<s; i++){
			a[i+1]=i;
		}
		long long ind=0;
		do{
			for(long long i=0; i<=s; i++){
				dp[i]=0;
			}
			long long ss=0;
			dp[0]=1;
			for(long long i=1; i<=s; i++){
				for(long long j=0; j<=i-1; j++){
					if(a[j]<=a[i]) dp[i]+=dp[j];
				}
			}
			for(long long i=0; i<=s; i++){
				ss+=dp[i];
			}
			if(ss==k){
				ind++;
				break;
			}
		}while(next_permutation(a+1, a+s+1));
		if(ind==0) s++;
		else{
			r++;
		}
	}
	for(long long i=1; i<=s; i++){
		v.push_back(a[i]);
	}
	return v;
}

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