Submission #594650

#	Time	Username	Problem	Language	Result	Execution time	Memory
594650		mohammad_kilani	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;


std::vector<int> construct_permutation(long long k){
	vector< int > ret;
	int mx = 0;
	while((1LL << (mx + 1)) <= k)
		mx++;
	int a = 0;
	for(int i = 0 ;i <= mx;i++){
		if(((k >> i) & 1) == 1)
			a++;
	}
	
	if(a <= 30){
		for(int i = 0 ;i < mx;i++)
			ret.push_back(i);
		k -= (1LL << mx);
		for(int i = mx - 1 ;i >= 0;i--){
			if(((k >> i) & 1) == 1)
				ret.insert(ret.begin() + i , (int)ret.size());
		}
		return ret;
	}
	

	vector< int > v;

	k -= (1LL << mx);

	int counter = 0;

	for(int a , b , i = 0 ;i < mx - 2;i++){
		a = ((k >> i) & 1);
		b = ((k >> (i + 1)) & 1);
		if(a == 0 || b == 0){
			ret.push_back(counter++);
			continue;
		}
		k -= (1LL << i);
		k -= (1LL << (i + 1));
		v.push_back(counter++);
		ret.push_back(counter++);
	}


	v.insert(v.begin() , counter + 1);
	v.insert(v.begin() , counter);
	counter+=2;

	ret.push_back(counter++);
	
	for(int i = mx - 1 ;i >= 0;i--){
		if(((k >> i) & 1) == 1)
			ret.insert(ret.begin() + i , counter++);
	}


	while((int)v.size() > 0){
		ret.push_back(v.back());
		v.pop_back();
	}

	return ret;
}

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