Submission #572977

#	Time	Username	Problem	Language	Result	Execution time	Memory
572977		JustAmethyst	Permutation (APIO22_perm)	C++17	0 / 100	1 ms	212 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int gre(ll x) {
	int j;
	ll y = 1, o = (ll)1;
	for (j = -1; (x+o) >= y; ++j) {
		y = y << 1;
	}
	return max(j, 0);
}

vector<int> construct_permutation(long long k)
{
	int z, m = 0, c;
	vector<int> v;
	ll y;
		
	vector<int> n;
	k -= 1;
	while (k > (ll)2) {
		z = gre(k);
		n.push_back(z);
		m += z;
      	y = 1 << z;
		k -= (y-1);
		if (k > (ll)3) --k;
	}
	m += max(sz(n)-1, 0);
	m += (int)k;
	c = m-1;
	for (int i = 0; i < sz(n); ++i) {
		for (int j = n[i]-1; j >= 0; --j) {
			v.push_back(c-j);
		}
		c -= n[i];
		if (i < sz(n)-1) {
			v.push_back(c);
			--c;
		}
	}

	for (int i = c; i >= 0; --i) v.push_back(i);
	
	return v;
}

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