結果

問題 No.1311 Reverse Permutation Index
ユーザー さかぽんさかぽん
提出日時 2020-12-10 15:50:08
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 30 ms / 1,500 ms
コード長 1,161 bytes
コンパイル時間 869 ms
コンパイル使用メモリ 110,292 KB
実行使用メモリ 25,152 KB
最終ジャッジ日時 2023-10-20 00:45:45
合計ジャッジ時間 1,867 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
25,152 KB
testcase_01 AC 28 ms
25,152 KB
testcase_02 AC 30 ms
25,152 KB
testcase_03 AC 28 ms
25,152 KB
testcase_04 AC 28 ms
25,152 KB
testcase_05 AC 29 ms
25,152 KB
testcase_06 AC 28 ms
25,152 KB
testcase_07 AC 28 ms
25,152 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class H
{
	static long[] ReadL() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
	static (long, long) Read2L() { var a = ReadL(); return (a[0], a[1]); }
	static void Main()
	{
		var (n, s) = ((long, int))Read2L();

		var a = ToSeq(n, s);
		a = Inverse(a);
		Console.WriteLine(ToIndex(a, s));
	}

	static int[] ToSeq(long index, int n)
	{
		var r = new List<int>();
		var ns = Enumerable.Range(0, n).ToList();

		var f = Factorial(n);
		for (int i = 0; i < n; i++)
		{
			f /= n - i;
			var ni = (int)(index / f);
			index %= f;
			r.Add(ns[ni]);
			ns.RemoveAt(ni);
		}
		return r.ToArray();
	}

	static long ToIndex(int[] a, int n)
	{
		var r = 0L;
		var ns = Enumerable.Range(0, n).ToList();

		var f = Factorial(n);
		for (int i = 0; i < n; i++)
		{
			f /= n - i;
			var ni = ns.IndexOf(a[i]);
			r += f * ni;
			ns.RemoveAt(ni);
		}
		return r;
	}

	static int[] Inverse(int[] a)
	{
		var r = new int[a.Length];
		for (int i = 0; i < a.Length; i++)
			r[a[i]] = i;
		return r;
	}

	static long Factorial(int n) { for (long x = 1, i = 1; ; x *= ++i) if (i >= n) return x; }
}
0