結果

問題 No.979 Longest Divisor Sequence
ユーザー nadeshinonadeshino
提出日時 2020-01-31 22:21:08
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,258 bytes
コンパイル時間 971 ms
コンパイル使用メモリ 72,880 KB
最終ジャッジ日時 2024-04-27 03:04:03
合計ジャッジ時間 1,334 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(53, 18) Error: type mismatch
Expression: N + 1
  [1] N: (int,)
  [2] 1: int literal(1)

Expected one of (first mismatch at [position]):
[1] func `+`[T](x, y: Complex[T]): Complex[T]
[1] func `+`[T](x, y: set[T]): set[T]
[1] func `+`[T](x: Complex[T]; y: T): Complex[T]
[1] proc `+`(x, y: float): float
[1] proc `+`(x, y: float32): float32
[1] proc `+`(x, y: int): int
[1] proc `+`(x, y: int16): int16
[1] proc `+`(x, y: int32): int32
[1] proc `+`(x, y: int64): int64
[1] proc `+`(x, y: int8): int8
[1] proc `+`(x, y: uint): uint
[1] proc `+`(x, y: uint16): uint16
[1] proc `+`(x, y: uint32): uint32
[1] proc `+`(x, y: uint64): uint64
[1] proc `+`(x, y: uint8): uint8
[1] proc `+`(x: float): float
[1] proc `+`(x: float32): float32
[1] proc `+`(x: int): int
[1] proc `+`(x: int16): int16
[1] proc `+`(x: int32): int32
[1] proc `+`(x: int64): int64
[1] proc `+`(x: int8): int8
[1] proc `+`[A](s1, s2: HashSet[A]): HashSet[A]
[2] func `+`[T](x: T; y: Complex[T]): Complex[T]

ソースコード

diff # 

import algorithm, complex, macros, math, sequtils, sets, strformat, strutils, sugar, tables

macro unpack*(rhs: seq, cnt: static[int]): auto =
  let v = genSym(); result = quote do:(let `v` = `rhs`;())
  for i in 0 ..< cnt: result[1].add(quote do:`v`[`i`])

template input*(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseint)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc `|=`*(n: var int, m: int) = n = n or m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
proc `%=`*(n: var int, m: int) = n = n mod m
proc `/=`*(n: var int, m: int) = n = n div m
proc `<<=`*(n: var int, m: int) = n = n shl m
proc `>>=`*(n: var int, m: int) = n = n shr m
proc `<?=`*(n: var SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))

# -------------------------------------------------- #

proc divisor(N: int): seq[int] =
  result = newSeq[int]()
  for i in 1 .. N:
    if i * i > N:
      break
    if N mod i == 0:
      result.add(i)
      if i * i != N:
        result.add(N div i)

let N = input(int)
let A = @[0] & input(seq[int])
var place = newSeq2[int](3 * 10 ^ 5 + 1, 0)
for k in 1 .. 3 * 10 ^ 5:
  place[k].add(0)
for i, a in A:
  place[a].add(i)
for k in 1 .. 3 * 10 ^ 5:
  place[k].add(N + 1)

var dp = newseq[int](N + 1)
for i in 1 .. N:
  if A[i] == 1:
    dp[i] = 1
    continue
  #echo divisor(A[i])
  for d in divisor(A[i]):
    if d == A[i]:
      continue
    var j = place[d][place[d].lowerBound(i) - 1]
    #echo place[d], " ", j
    dp[i] >?= dp[j] + 1
echo max(dp)
#echo dp
0