Submission #1202960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202960		Kavelmydex	Permutation (APIO22_perm)	C++20	79.68 / 100	5 ms	1092 KiB

perm

/*
k--;
seperate (k-1) to the sum of (2^i-1)
==========================
==========================
*/
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define vi vector<ll>  
#define pi pair<ll,ll>
#define pb push_back
#define sz(x) ((ll)x.size())
#define sp ' '
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define rep(i,x,n) for(ll i=x; i<=n; ++i)
#define For(i,n) rep(i,0,n-1)   
#define ff first 
#define ss second
#define ld long double
#define mp make_pair

const int N=100,OO=2e9,mod=1e9+7;  
const int dx[]{0,0,-1,1}, dy[]{1,-1,0,0};

void cmn(int &a,int b){a = min(a,b);}
void cmx(int &a,int b){a = max(a,b);}

ll p[N], h[N][2];
vector<int>construct_permutation(ll k){
	k--;
	ll n=0; p[0]=1;
	vector<int>ans;
	vi v{0};
	for(int i=1;i<=59;++i) p[i]=p[i-1]*2,v.pb(p[i]-1), h[i][0]=h[i][1]=0;
	for(int i=59;i>=1;--i){
		while(k>=v[i]){
			h[i][0]++; n+=i;
			k-=v[i];
		}
		if(i>=2){
			while(k>=v[i]-p[i-2]){
				k-=v[i]-p[i-2];
				n+=i; h[i][1]++;
			}
		}
	} assert(!k); 
	n--;
	for(int i=1;i<=59;++i){
		For(j,h[i][0]){
			vi toadd;
			for(int k=0;k<i;++k) toadd.pb(n--);
			reverse(begin(toadd),end(toadd));
			for(int x:toadd)ans.pb(x);
		} 
		if(h[i][1]){
			assert(h[i][1]==1);
			vi toadd;
			For(k,i) toadd.pb(n--);
			reverse(begin(toadd),end(toadd));
			swap(toadd.back(),toadd[toadd.size()-2]);
			for(int x:toadd) ans.pb(x);
		}
	}
	return ans;
}	

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