Submission #1202494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202494		trashaccount	Permutation (APIO22_perm)	C++20	81 / 100	659 ms	812 KiB

perm

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

#define ll long long
#define isz(a) (int)(a).size()

const int NM = 90, MX = 1e9;
const ll LIM = 1e18;

ll dp[NM+5], bit[NM+5];

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

void update(int x, ll val){
	while (x <= NM){
		bit[x] += val;
		x += x & (-x);
	}
}

ll get(int x){
	ll res = 0;
	while (x > 0){
		res += bit[x];
		x -= x & (-x);
	}
	return res;
}

ll calc(vector <int> &p){
	memset(dp, 0, sizeof(dp));
	memset(bit, 0, sizeof(bit));
	for (int i = 0; i < isz(p); i++){
		dp[i] = 1+get(p[i]);
		update(p[i]+1, dp[i]);
	}
	ll res = 1;
	for (int i = 0; i < isz(p); i++) res += dp[i];
	return res;
}

vector <int> solve(ll k){
	int sz = 1;
	while ((1LL<<sz) < k) sz++;

	vector <int> p = {}, pbest = {};
	ll best = -1;
	for (int i = 0; i < sz; i++) p.push_back(i);
	for (int iter = 1; iter <= 500 || best == -1; iter++){
		shuffle(p.begin(), p.end(), rng);
		ll tmp = calc(p);
		if (tmp <= k){
			if (tmp > best){
				best = tmp;
				pbest = p;
			}
		}
	}
	p = pbest;
	while (true){
		bool chk = 0;
		for (int i = 0; i+1 < sz; i++){
			if (p[i] < p[i+1]) continue;
			swap(p[i], p[i+1]);
			if (calc(p) > k) swap(p[i], p[i+1]);
			else chk = 1;
		}
		if (!chk) break;
	}

	ll res = calc(p);
	if (res == k) return p;
	vector <int> q = solve(k-res+1);
	for (int &x : p) x += isz(q);
	for (int x : q) p.push_back(x);
	return p;
}

vector <int> construct_permutation(ll k){
	if (k <= 90){
		vector <int> res = {};
		for (int i = k-2; i >= 0; i--)
			res.push_back(i);
		return res;
	}
	return solve(k);
}

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