結果
問題 | No.1311 Reverse Permutation Index |
ユーザー |
![]() |
提出日時 | 2020-12-08 14:06:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,500 ms |
コード長 | 1,639 bytes |
コンパイル時間 | 759 ms |
コンパイル使用メモリ | 94,076 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-17 14:37:44 |
合計ジャッジ時間 | 1,202 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
/* -*- coding: utf-8 -*-** 1311.cc: No.1311 Reverse Permutation Index - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_S = 20;/* typedef */typedef unsigned long long ull;/* global variables */ull fs[MAX_S + 1];int ds[MAX_S], ps[MAX_S];bool used[MAX_S];/* subroutines */int getunused(int s, int k) {for (int i = 0; i < s; i++)if (! used[i]) {if (k == 0) return i;k--;}return -1;}int countunused(int d) {int c = 0;for (int i = 0; i < d; i++)if (! used[i]) c++;return c;}/* main */int main() {ull n;int s;scanf("%llu%d", &n, &s);fs[0] = 1;for (int i = 1; i <= s; i++) fs[i] = fs[i - 1] * i;//for (int i = 0; i <= s; i++) printf("fs(%d)=%llu\n", i, fs[i]);memset(used, false, sizeof(used));for (int i = 0; i < s; i++) {int k = n / fs[s - 1 - i];ds[i] = getunused(s, k);used[ds[i]] = true;n -= k * fs[s - 1 - i];}//for (int i = 0; i < s; i++) printf("%d ", ds[i]); putchar('\n');for (int i = 0; i < s; i++) ps[ds[i]] = i;//for (int i = 0; i < s; i++) printf("%d ", ps[i]); putchar('\n');memset(used, false, sizeof(used));ull m = 0;for (int i = 0; i < s; i++) {m += countunused(ps[i]) * fs[s - 1 - i];used[ps[i]] = true;}printf("%llu\n", m);return 0;}