Submission #1061371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061371		Gangsta	Permutation (APIO22_perm)	C++17	71.22 / 100	8 ms	1512 KiB

perm

#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()
 
using namespace std;
 
ll tap(int n){
	ll sum = 0;
	for(int i = 0; i < n; i++){
		ll x = (1LL<<i);
		sum += x;
	}
	return sum;
}
 
vector <int> construct_permutation(ll k){
	k--;
	int cnt = 0;
	deque <int> d;
	vector <int> v;
	while(k>0){
		int l = 1, r = 58, md, jog = -1;
		ll jog1 = -1;
		while(l <= r){
			md = (l+r)/2;
			ll san = tap(md);
			if(san <= k){
				jog = md;
				jog1 = san;
				l = md + 1;
			}
			else r = md - 1;
		}
		if(jog != -1){
			k -= jog1;
			for(int i = cnt+jog-1; i >= cnt; i--) d.push_front(i);
			cnt += jog;
		}
	}
	while(!d.empty()){
		v.pb(d.front());
		d.pop_front();
	}
	return v;
}

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