Submission #786640

#	Time	Username	Problem	Language	Result	Execution time	Memory
786640		mindiyak	Permutation (APIO22_perm)	C++17	71.22 / 100	11 ms	1364 KiB

perm

#include "perm.h"
#include <cmath>
#include <deque>
#include <iostream>
#include <algorithm>
#define ll unsigned long long
#define pb push_back
using namespace std;


std::vector<int> construct_permutation(long long k)
{
	if(k == 0){
		return vector<int>(0);
	}k--;
	vector<ll> powers;
	for(ll i=0;i<64;i++){
	// for(int i=0;i<10;i++){
		powers.pb(pow(2,i)-1);
		// cout << i << " " << powers[i] << endl;
	}
	deque<pair<ll,ll>> arr;
	ll n=0;
	while(k > 0){
		ll length = upper_bound(powers.begin(),powers.end(),k) - powers.begin();
		if(length != 0){
			length --;
		}
		arr.push_front({n,n+length});
		// cout << k << " " << n << " to " << n + length << " " << (ll)powl(2,length)-1 <<endl;
		n += length;
		k -= (ll)powl(2,length)-1;
	}
	vector<int> ans;
	for(ll i=0;i<arr.size();i++){
		for(ll j=arr[i].first;j<arr[i].second;j++){
			ans.pb(j);
			// cout << j << " ";
		}
	}
	// cout << endl;
	return ans;
}

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