Submission #577343

#	Time	Username	Problem	Language	Result	Execution time	Memory
577343		handlename	Permutation (APIO22_perm)	C++17	100 / 100	7 ms	364 KiB

perm

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+7;
int n;
bool prime[1001];
bool lmao;
vector<int> primes;
vector<int> construct_permutation(long long k){
	vector<int> temp;
	if (k==1) return temp;
	temp.pb(0);
	if (k==2) return temp;
	if (!lmao){
		memset(prime,true,sizeof(prime));
		lmao=true;
		for (int p=2;p<1001;p++){
			if (prime[p]){
				primes.pb(p);
				for (int i=p*2;i<1001;i+=p){
					prime[i]=false;
				}
			}
		}
	}
	for (auto p:primes){
		if (k%p==0 && k>p){
			vector<int> a=construct_permutation(p);
			int sz=a.size();
			vector<int> b=construct_permutation(k/p);
			for (auto i:b) a.pb(i+sz);
			return a;
		}
	}
	vector<int> lol=construct_permutation(k/2);
	lol.pb(lol.size());
	if (k%2==1){
		temp.clear();
		temp.pb(lol.size());
		for (auto i:lol) temp.pb(i);
		return temp;
	}
	return lol;
}

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