Submission #786662

#	Time	Username	Problem	Language	Result	Execution time	Memory
786662		mindiyak	Permutation (APIO22_perm)	C++17	89.43 / 100	9 ms	444 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;
	}
	
	vector<int> ans;
	ll n=0;
	while(k > 0){
		ll length = upper_bound(powers.begin(),powers.end(),k) - powers.begin();
		if(length != 0){
			length --;
		}
		// cout << "k-" << k << " n-" << n << " lenght-" <<  length << " minus-" << (ll)powl(2,length)-1 <<endl;
		if(n == 0){
			for(ll j=0;j<length;j++){
				ans.pb(j);
			}
			n += length;


			// cout << " ans - > ";
			// for(ll j=0;j<ans.size();j++){
			// 	cout << ans[j] << " ";
			// }cout << endl;

		}else{
			ans.insert(ans.begin()+length-1,n);
			n++;

			// cout << " ans - > ";
			// for(ll j=0;j<ans.size();j++){
			// 	cout << ans[j] << " ";
			// }cout << endl;
			 
			k+=(ll)powl(2,length-1)-1;
		}
		// cout << k << " " << n << " to " << n + length << " " << (ll)powl(2,length)-1 <<endl;
		
		k -= (ll)powl(2,length)-1;
	}

	return ans;
}

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