Submission #1291600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291600		dosts	Permutation (APIO22_perm)	C++20	100 / 100	3 ms	580 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;


void doit(deque<signed>& dq,int k,int& cur) {
	if (!k) return;
	if (k == 1) {
		dq.push_front(cur++);
		return;
	}
	for (int j = 1;j<100 && (k+1)/(j+1)>1;j++) {
		if ((k+1)%(j+1)) continue;
		deque<signed> dq1{},dq2{};
		doit(dq1,(k+1)/(j+1)-1,cur);
		doit(dq2,j,cur);
		while (!dq1.empty()) dq.push_back(dq1.front()),dq1.pop_front();
		while (!dq2.empty()) dq.push_back(dq2.front()),dq2.pop_front();
		return;
	}
	doit(dq,k-1,cur);
	dq.push_front(cur++);
}

std::vector<signed> construct_permutation(int k)
{
	k--;
	deque<signed> dq;
	int cur = 0;
	doit(dq,k,cur);
	return vector<signed>(all(dq));
}

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