Submission #596984

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

perm

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

vi tr(long long k, int off){
	vi a;
	int cnt=62;
	long long qq = (1LL<<off);
	if(k<qq) return vi(5000, 0);
	k-=qq;
	while(k>0 && cnt>off){
		while(k>=(1LL<<cnt)-qq){
			k-=((1LL<<cnt)-qq);
			a.push_back(cnt-off);
		}
		cnt--;
	}
	//cout<<k<<" left"<<endl;
	vi b;
	int p=off-1;
	for(auto v : a){
		for(int i=p+v;i>p;i--){
			b.push_back(i);
		}
		p = p+v;
	}
	for(int i=off-1;i>=0;i--) b.push_back(i);
	while(k) b.push_back(++p), k--;
	reverse(b.begin(), b.end());

	return b;
}

vector<int> construct_permutation(long long k)
{
	vi ans;
	int cnt=61;
	int aa=0;
	vi ins;
	while(cnt>=0){
		if(k&(1LL<<cnt)){
			ins.push_back(cnt);
			if(ans.size()==0){
				for(int i=0;i<cnt;i++) ans.push_back(i);
				aa = cnt;
			}
			else{
				ans.insert(ans.begin()+cnt, aa++);
			}
		}
		cnt--;
	}
	/*
	for(int i=0;i<20;i++){
		vi b = tr(k, i);
		if(b.size()<ans.size() || ans.size()==0) ans = b;
	}*/
	return ans;
}

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