Submission #897020

#	Time	Username	Problem	Language	Result	Execution time	Memory
897020		d4xn	Permutation (APIO22_perm)	C++17	71.22 / 100	582 ms	1484 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5e3+3, M = 3e2+2, X = 3e2+2;
const ll L = 62;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> construct_permutation(ll k)
{	
	vector<int> p;
	if (!k) return p;
	ll K = k;
	k--;

		int r = N;
		//vector<int> p2;
		for (int j = L; j > 0; j--) {
			//cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl;
			if (k >= (1ll << j) - 1ll) {
				k -= (1ll << j) - 1ll;
				for (int l = 1; l <= j; l++) {
					/*p2*/p.push_back(r-j+l);
				}
				//cerr << j << endl;
				r -= j;
				j = L+1;
			}
		}

		/*if (p.empty() || p2.size() < p.size()) swap(p, p2);
	}*/

	for (int i = 1; i <= M; i++) {
		// cojo i subsequences
		// he de sumar k+i-1
		ll nwK = K + i - 1;
		int cnt[L+1];
		for (int j = L; j >= 0; j--) {
			cnt[j] = (((nwK >> j) & 1) ? 1 : 0);
		}
		
		int c = __builtin_popcountl(nwK);
		while (c < i) {
			bool b = 0;
			for (int j = L; j > 0; j--) {
				if (cnt[j]) {
					cnt[j-1] += 2;
					cnt[j]--;
					c++;
					b = 1;
					break;
				}
			}

			if (!b) break;
		}

		if (c != i) continue;
//cerr << "cojo " << i << endl;
		r = N;
		vector<int> p2;
		for (int j = L; j >= 0; j--) {
			while (cnt[j]--) {
				for (int l = 1; l <= j; l++) {
					p2.push_back(r-j+l);
					//cerr << r-j+l << endl;
				}
				r -= j;
			}
		}

		if (p.empty() || p2.size() < p.size()) swap(p, p2);
	}

	for (int tt = 0; tt < X; tt++) {
		k = K-1;
	r = N;
		vector<int> p2;
		for (int j = L; j > 0; j--) {
			//cerr << k << " " << j << " " << (1ll << j) << " " << (1ll << j) - 1ll << endl;
			if (k >= (1ll << j) - 1ll && rng() % 3 == 2) {
				k -= (1ll << j) - 1ll;
				for (int l = 1; l <= j; l++) {
					p2.push_back(r-j+l);
				}
				//cerr << j << endl;
				r -= j;
				j = L+1;
			}

			if (k && j == 1) j = L+1;
		}
		if (p.empty() || p2.size() < p.size()) swap(p, p2);
	}

	int sz = p.size();
	for (int i = 0; i < sz; i++) {
		p[i] -= N-sz+1;
	}

	return p;
}

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