Submission #1202511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202511		trashaccount	순열 (APIO22_perm)	C++20	89.92 / 100	46 ms	328 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 = 200, MX = 1e9;
const ll LIM = 1e18;

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

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

int get_rand(int l, int r){
	int tmp = rng()%(r-l+1);
	if (tmp < 0) tmp += r-l+1;
	return l + tmp;
}

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> construct_permutation(ll k){
	vector <int> p = {0};
	while (calc(p) < k){
		int l = 1, r = isz(p), res = 0;
		while (l <= r){
			int mid = (l+r)/2;
			vector <int> p_nxt = p;
			for (int &x : p_nxt)
				if (x >= mid) x++;
			p_nxt.push_back(mid);
			if (calc(p_nxt) <= k){
				res = mid;
				l = mid+1;
			}
			else r = mid-1;
		}
		if (res > 0 && rng()%2 != 0) res--;
		for (int &x : p) if (x >= res) x++;
		p.push_back(res);
	}
	return p;
}

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