結果
| 問題 | No.3441 Sort Permutation 2 |
| コンテスト | |
| ユーザー |
 kemuniku
|
| 提出日時 | 2026-02-06 21:56:06 |
| 言語 | Nim (2.2.6) |
| 結果 |
AC
|
| 実行時間 | 616 ms / 2,000 ms |
| コード長 | 13,336 bytes |
| 記録 | |
| コンパイル時間 | 8,208 ms |
| コンパイル使用メモリ | 97,108 KB |
| 実行使用メモリ | 25,880 KB |
| 最終ジャッジ日時 | 2026-02-06 21:56:23 |
| 合計ジャッジ時間 | 16,232 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 41 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
ImportExpand "cplib/tmpl/sheep.nim" <=== "when not declared CPLIB_TMPL_SHEEP:\n const CPLIB_TMPL_SHEEP* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import algorithm\n import sequtils\n import tables\n import macros\n import math\n import sets\n import strutils\n import strformat\n import sugar\n import heapqueue\n import streams\n import deques\n import bitops\n import std/lenientops\n import options\n #入力系\n proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n proc si(): string {.inline.} =\n result = \"\"\n var c: char\n while true:\n c = getchar()\n if c == ' ' or c == '\\n' or c == '\\255':\n break\n result &= c\n #chmin,chmax\n template `max=`(x, y) = x = max(x, y)\n template `min=`(x, y) = x = min(x, y)\n proc chmin[T](x: var T, y: T):bool=\n if x > y:\n x = y\n return true\n return false\n proc chmax[T](x: var T, y: T):bool=\n if x < y:\n x = y\n return true\n return false\n #bit演算\n proc `%`*(x: int, y: int): int =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x: int, y: int): int{.inline.} =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and result * y < x: result -= 1\n proc `%=`(x: var int, y: int): void = x = x%y\n proc `//=`(x: var int, y: int): void = x = x//y\n proc `**`(x: int, y: int): int = x^y\n proc `**=`(x: var int, y: int): void = x = x^y\n proc `^`(x: int, y: int): int = x xor y\n proc `|`(x: int, y: int): int = x or y\n proc `&`(x: int, y: int): int = x and y\n proc `>>`(x: int, y: int): int = x shr y\n proc `<<`(x: int, y: int): int = x shl y\n proc `~`(x: int): int = not x\n proc `^=`(x: var int, y: int): void = x = x ^ y\n proc `&=`(x: var int, y: int): void = x = x & y\n proc `|=`(x: var int, y: int): void = x = x | y\n proc `>>=`(x: var int, y: int): void = x = x >> y\n proc `<<=`(x: var int, y: int): void = x = x << y\n proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n #便利な変換\n proc `!`(x: char, a = '0'): int = int(x)-int(a)\n #定数\n #[ include cplib/utils/constants ]#\n when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 1001000027.int32\n const INF64*: int = int(3300300300300300491)\n const INF = INF64\n #converter\n\n #range\n iterator range(start: int, ends: int, step: int): int =\n var i = start\n if step < 0:\n while i > ends:\n yield i\n i += step\n elif step > 0:\n while i < ends:\n yield i\n i += step\n iterator range(ends: int): int = (for i in 0..<ends: yield i)\n iterator range(start: int, ends: int): int = (for i in\n start..<ends: yield i)\n\n #joinが非stringでめちゃくちゃ遅いやつのパッチ\n proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n proc dump[T](arr:seq[seq[T]])=\n for i in 0..<len(arr):\n echo arr[i]\n\n proc sum(slice:HSlice[int,int]):int=\n return (slice.a+slice.b)*len(slice)//2\n \n proc `<`[T](l,r:seq[T]):bool=\n for i in 0..<min(len(l),len(r)):\n if l[i] > r[i]:\n return false\n elif l[i] < r[i]:\n return true\n return len(l) < len(r)\n"
ImportExpand "cplib/collections/group_unionfind.nim" <=== "when not declared CPLIB_COLLECTIONS_UNIONFIND:\n const CPLIB_COLLECTIONS_UNIONFIND* = 1\n import algorithm\n import sequtils\n type UnionFind* = ref object\n count*: int\n par_or_siz: seq[int]\n next : seq[int]\n edge_cnt : seq[int]\n proc initUnionFind*(N: int): UnionFind =\n result = UnionFind(count: N, par_or_siz: newSeqwith(N, -1),next:(0..<N).toseq(),edge_cnt:newseqwith(N,0))\n proc root*(self: UnionFind, x: int): int =\n if self.par_or_siz[x] < 0:\n return x\n else:\n self.par_or_siz[x] = self.root(self.par_or_siz[x])\n return self.par_or_siz[x]\n proc issame*(self: UnionFind, x: int, y: int): bool =\n return self.root(x) == self.root(y)\n proc unite*(self: UnionFind, x: int, y: int) =\n var x = self.root(x)\n var y = self.root(y)\n if(x != y):\n swap(self.next[x],self.next[y])\n if(self.par_or_siz[x] > self.par_or_siz[y]):\n swap(x, y)\n self.par_or_siz[x] += self.par_or_siz[y]\n self.par_or_siz[y] = x\n self.edge_cnt[x] += self.edge_cnt[y]\n self.count -= 1\n self.edge_cnt[x] += 1\n proc siz*(self: UnionFind, x: int): int =\n var x = self.root(x)\n return -self.par_or_siz[x]\n proc roots*(self:UnionFind):seq[int]=\n ## O(N)かけて、rootになっている頂点を列挙します。\n ## 注意:O(root数)でないことに注意してください。\n for i in 0..<len(self.par_or_siz):\n if self.par_or_siz[i] < 0:\n result.add(i)\n proc get_group*(self:UnionFind,x:int):seq[int]=\n var now = x\n while true:\n result.add(now)\n now = self.next[now]\n if now == x:\n break\n proc groups*(self: UnionFind): seq[seq[int]] =\n for root in self.roots():\n result.add(self.get_group(root))\n proc edge_count*(self: UnionFind, x: int): int =\n ## xの属するグループの辺の数を返します。\n var x = self.root(x)\n return self.edge_cnt[x]\n proc is_tree*(self: UnionFind, x: int): bool =\n ## xの属する連結成分が木かどうかを返します。\n var x = self.root(x)\n return self.edge_cnt[x] == self.siz(x) - 1\n proc is_namori*(self: UnionFind, x: int): bool =\n ## xの属する連結成分がなもりグラフかどうかを返します。\n var x = self.root(x)\n return self.edge_cnt[x] == self.siz(x)\n proc has_cycle*(self: UnionFind, x: int): bool =\n ## xの属する連結成分にサイクルがあるかどうかを返します。\n var x = self.root(x)\n return self.edge_cnt[x] >= self.siz(x)\n proc copy*(self:UnionFind):UnionFind=\n result = UnionFind(count: self.count, par_or_siz: self.par_or_siz,next:self.next)\n"
ImportExpand "cplib/math/divisor.nim" <=== "when not declared CPLIB_MATH_DIVISOR:\n const CPLIB_MATH_DIVISOR* = 1\n import sequtils\n import tables\n import algorithm\n #[ import cplib/math/primefactor ]#\n when not declared CPLIB_MATH_PRIMEFACTOR:\n const CPLIB_MATH_PRIMEFACTOR* = 1\n #[ import cplib/math/inner_math ]#\n when not declared CPLIB_MATH_INNER_MATH:\n const CPLIB_MATH_INNER_MATH* = 1\n proc add*(a, b, m: int): int {.importcpp: \"((__int128)(#) + (__int128)(#)) % (__int128)(#)\", nodecl.}\n proc mul*(a, b, m: int): int {.importcpp: \"(__int128)(#) * (__int128)(#) % (__int128)(#)\", nodecl.}\n #[ import cplib/math/isprime ]#\n when not declared CPLIB_MATH_ISPRIME:\n const CPLIB_MATH_ISPRIME* = 1\n #[ import cplib/math/powmod ]#\n when not declared CPLIB_MATH_POWMOD:\n const CPLIB_MATH_POWMOD* = 1\n #[ import cplib/math/inner_math ]#\n proc powmod*(a, n, m: int): int =\n assert m != 0\n if m == 1:\n return 0\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n mod 2 != 0: rev = mul(rev, a, m)\n if n > 1: a = mul(a, a, m)\n n = n shr 1\n return rev\n proc isprime*(N: int): bool =\n let bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]\n if N == 2:\n return true\n if N < 2 or (N and 1) == 0:\n return false\n let N1 = N-1\n var d = N1\n var s = 0\n while (d and 1) == 0:\n d = d shr 1\n s += 1\n for a in bases:\n var t: int\n if a mod N == 0:\n continue\n t = powmod(a, d, N)\n if t == 1 or t == N1:\n continue\n block test:\n for _ in 0..<(s-1):\n t = powmod(t, 2, N)\n if t == N1:\n break test\n return false\n return true\n #[ import cplib/str/run_length_encode ]#\n when not declared CPLIB_STR_RUN_LENGTH_ENCODE_UTILS:\n const CPLIB_STR_RUN_LENGTH_ENCODE_UTILS* = 1\n import sequtils\n proc run_length_encode*[T](a: seq[T]): seq[(T, int)] =\n for i in 0..<len(a):\n if result.len == 0:\n result.add((a[i], 1))\n continue\n if result[^1][0] == a[i]: result[^1][1] += 1\n else: result.add((a[i], 1))\n \n proc run_length_encode*(s: string): seq[(char, int)] =\n var a = s.items.toSeq\n return run_length_encode(a)\n import random\n import std/math\n import algorithm\n import tables\n \n randomize()\n proc find_factor(n: int): int =\n if not ((n and 1) != 0): return 2\n if isprime(n): return n\n const m = 128\n while true:\n var x, ys, q, r, g = 1\n var rnd, y = rand(0..n-3) + 2\n proc f(x: int): int = add(mul(x, x, n), rnd, n)\n while g == 1:\n x = y\n for i in 0..<r: y = f(y)\n for k in countup(0, r-1, m):\n ys = y\n for _ in 0..<min(m, r-k):\n y = f(y)\n q = mul(q, abs(x-y), n)\n g = gcd(q, n)\n if g != 1: break\n r = r shl 1\n if g == n:\n g = 1\n while g == 1:\n ys = f(ys)\n g = gcd(n, abs(x - ys))\n if g < n:\n if isprime(g): return g\n elif isprime(n div g): return n div g\n return find_factor(g)\n \n proc primefactor*(n: int, sorted: bool = true): seq[int] =\n var n = n\n while n > 1 and not isprime(n):\n var p = find_factor(n)\n while n mod p == 0:\n result.add(p)\n n = n div p\n if n > 1: result.add(n)\n if sorted: return result.sorted\n \n proc primefactor_table*(n: int): Table[int, int] =\n for p in primefactor(n):\n if p in result: result[p] += 1\n else: result[p] = 1\n \n proc primefactor_tuple*(n: int): seq[(int, int)] = primefactor(n, true).run_length_encode\n proc divisor_naive(x: int, sorted: bool): seq[int] =\n for i in 1..x:\n if i*i > x: break\n if x mod i == 0:\n result.add(i)\n if i*i != x:\n result.add(x div i)\n if sorted: result.sort\n\n proc divisor*(x: int, sorted: bool = true): seq[int] =\n if x <= 1000_000: return divisor_naive(x, sorted)\n var factor = primefactor(x).toCountTable.pairs.toSeq\n var ans = newSeq[int](0)\n proc dfs(d, x: int) =\n if d == factor.len:\n ans.add(x)\n return\n var mul = 1\n for i in 0..factor[d][1]:\n dfs(d+1, x*mul)\n if i != factor[d][1]: mul *= factor[d][0]\n dfs(0, 1)\n if sorted: ans.sort\n return ans\n"
var N = ii()
var P = lii(N).mapit(it-1)
var uf = initUnionFind(N)
var A = newseqwith(N,-1)
for i in range(N):
A[i] = abs(P[i]-i)
uf.unite(i,P[i])
var ans = newseqwith(N,0)
for g in groups(uf):
var tmp = 0
for i in g:
tmp = gcd(tmp,A[i])
#echo tmp
for x in divisor(tmp):
ans[x] += len(g)-1
echo ans[1..<N].join("\n")