結果
問題 |
No.1311 Reverse Permutation Index
|
ユーザー |
![]() |
提出日時 | 2021-05-07 16:38:29 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 53 ms / 1,500 ms |
コード長 | 2,781 bytes |
コンパイル時間 | 2,755 ms |
コンパイル使用メモリ | 77,664 KB |
実行使用メモリ | 37,036 KB |
最終ジャッジ日時 | 2024-09-15 05:01:11 |
合計ジャッジ時間 | 3,865 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
import java.io.*; import java.util.*; public class Main { static long[] values; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(); long x = sc.nextLong(); int size = sc.nextInt(); values = new long[size]; for (int i = 0; i < size; i++) { values[i] = kaijo(size - i); } int[] perm = getPerm(x, size); int[] reverse = getReverse(perm); long ans = getOrder(reverse); System.out.println(ans); } static long getOrder(int[] reverse) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 1; i <= reverse.length; i++) { list.add(i); } long order = 0; for (int i = 0; i < reverse.length - 1; i++) { for (int j = 0; j < list.size(); j++) { if (reverse[i] == list.get(j)) { order += values[i + 1] * j; list.remove(j); break; } } } return order; } static int[] getReverse(int[] perm) { int[] reverse = new int[perm.length]; for (int i = 1; i <= perm.length; i++) { for (int j = 0; j < perm.length; j++) { if (perm[j] == i) { reverse[i - 1] = j + 1; break; } } } return reverse; } static int[] getPerm(long order, int size) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 1; i <= size; i++) { list.add(i); } int[] perm = new int[size]; for (int i = 0; i < size - 1; i++) { int idx; if (values[i + 1] <= order) { idx = (int)(order / values[i + 1]); order %= values[i + 1]; } else { idx = 0; } perm[i] = list.remove(idx); } perm[size - 1] = list.get(0); return perm; } static long kaijo(int x) { if (x == 0) { return 1; } else { return x * kaijo(x - 1); } } } class Scanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); public Scanner() throws Exception { } public int nextInt() throws Exception { return Integer.parseInt(next()); } public long nextLong() throws Exception { return Long.parseLong(next()); } public String next() throws Exception { if (!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } }