제출 #1202513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202513		trashaccount	Permutation (APIO22_perm)	C++20	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 = 1000, 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){
	if (k <= 90){
		vector <int> res = {};
		for (int i = k-2; i >= 0; i--)
			res.push_back(i);
		return res;
	}
	vector <int> p = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 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;
		}
		for (int &x : p) if (x >= res) x++;
		p.push_back(res);
	}
	return p;
}

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