백준 1722번 [순열의 순서]

팩토리얼을 이용한 순열 구현

next_permutation보다 시간복잡도 빠름

ll fac[21];
vector<ll> v;
bool visited[21] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, q;
	cin >> n >> q;
	fac[0] = 1;
	for (int i = 1; i <= 20; i++) {
		fac[i] = fac[i - 1] * i;
	}

	if (q == 1) {
		ll k;
		cin >> k;
		for (int i = n-1; i >= 0; i--) {
			ll cnt = 1;
			for (int j = 1; j <= n; j++) {
				if (visited[j]) {
					continue;
				}
				if (k <= cnt * fac[i]) {
					k -= ((cnt - 1) * fac[i]);
					v.push_back(j);
					visited[j] = true;
					break;
				}
				cnt++;
			}
		}
		for (int i = 0; i < n; i++) {
			cout << v[i] << " ";
		}
	}
	else if (q == 2) {
		ll ans = 1;
		for (int i = 0; i < n; i++) {
			ll x;
			ll cnt = 0;
			cin >> x;
			v.push_back(x);
			for (int j = 1; j < v[i]; j++) {
				if (visited[j] == false) {
					cnt++;
				}
			}
			ans += cnt * fac[n - 1 - i];
			visited[x] = true;
		}
		cout << ans;
	}
	return 0;
}