結果

問題 No.1311 Reverse Permutation Index
ユーザー dot_haraai
提出日時 2021-05-29 16:50:55
言語 Nim
(2.2.0)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 1,768 bytes
コンパイル時間 4,454 ms
コンパイル使用メモリ 86,528 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 00:08:47
合計ジャッジ時間 5,092 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 18) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'times' [UnusedImport]
/home/judge/data/code/Main.nim(2, 26) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(1, 25) Warning: imported and not used: 'sequtils' [UnusedImport]
/home/judge/data/code/Main.nim(2, 37) Warning: imported and not used: 'deques' [UnusedImport]
/home/judge/data/code/Main.nim(1, 41) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(1, 52) Warning: imported and not used: 'tables' [UnusedImport]
/home/judge/data/code/Main.nim(1, 60) Warning: imported and not used: 'sets' [UnusedImport]
/home/judge/data/code/Main.nim(1, 66) Warning: imported and not used: 'lists' [UnusedImport]
/home/judge/data/code/Main.nim(1, 73) Warning: imported and not used: 'intsets' [UnusedImport]
/home/judge/data/code/Main.nim(2, 8) Warning: imported and not used: 'critbits' [UnusedImport]
/home/judge/data/code/Main.nim(2, 18) Warning: imported and not used: 'future' [UnusedImport]

ソースコード

diff # 

import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
template `mod=`(x,y) = x = x mod y
template scan2 = (scan(), scan())
template scan3 = (scan(), scan())
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc scanf(): float = read().parseFloat
proc toInt(c:char): int =
    return int(c) - int('0')


proc fact(n:int):int=
  if n==0:
    return 1
  if n==1:
    return 1
  else:
    return n*fact(n-1)


proc getIdx(v:seq[int]):int=
  var
    n = v.len
    avlNum = newseq[int](n)
  result=1
  for i in 1..n:
    avlNum[i-1]=i
  for digit in 0..<n:
    for idx, num in avlNum:
      if v[digit]==num:
        result+=idx*fact(n-digit-1)
        avlNum.delete(idx)
        break



proc getSeq(n:int,v:int):seq[int]=
  result = newseq[int]()
  var cum = 0
  for digit in 1..n:# digit桁目まで決まった場合
    #echo "digit: ", digit, " cum:", cum, " result:", result
    var avlNum = newseq[int]()
    for i in 1..n:
      if i notin result:
        avlNum.add(i)
    #echo avlNum
    # avlNumに入っている数字は使っていい
    for idx, num in avlNum:
      #echo fmt"{idx} , {cum} + {fact(n-digit)}"
      if v > cum+fact(n-digit):
        cum+=fact(n-digit)
      else:
        result.add(num)
        break

proc getInv(v:seq[int]):seq[int]=
  var n = v.len
  result = newseq[int](n)
  for i in 0..<n:
    result[v[i]-1] = i+1

#echo getSeq(5,51)
#echo getSeq(5,51).getInv
#echo getSeq(5,51).getInv.getIdx

proc solve():int=
  var
    n = scan()+1
    s = scan()
  return getSeq(s,n).getInv.getIdx-1

  

echo solve()
0