結果
問題 |
No.1013 〇マス進む
|
ユーザー |
![]() |
提出日時 | 2023-01-20 18:38:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 339 ms / 2,000 ms |
コード長 | 2,140 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 140,696 KB |
最終ジャッジ日時 | 2024-06-23 07:08:52 |
合計ジャッジ時間 | 15,551 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
from typing import List, Generic, Optional, Callable, TypeVar S = TypeVar('S') class FunctionalGraph(Generic[S]): def __init__(self, n: int, edge_to: List[S], node_val: Optional[List[S]] = None, nxt_node_val: Optional[List[S]] = None, op: Optional[Callable[[int, int], int]] = lambda fr, to: to) -> None: if node_val is None: node_val = list(range(n)) if nxt_node_val is None: nxt_node_val = [node_val[edge_to[i]] for i in range(n)] self.n = n self.edge_to = edge_to self.node_val = node_val self.nxt_node_val = nxt_node_val self.op = op self.built = False def build_doubling(self, bit_max: int = 31): self.built = True self.bit_max = bit_max self.dub = [[-1] * self.n for _ in range(self.bit_max)] self.dp = [[-1] * self.n for _ in range(self.bit_max)] for i in range(self.n): self.dub[0][i] = self.edge_to[i] self.dp[0][i] = self.nxt_node_val[i] for i in range(1, self.bit_max): for j in range(self.n): if self.dub[i - 1][j] != -1: self.dub[i][j] = self.dub[i - 1][self.dub[i - 1][j]] self.dp[i][j] = self.op(self.dp[i - 1][j], self.dp[i - 1][self.dub[i - 1][j]]) def get(self, v: int, k: int) -> int: if not self.built: self.build_doubling() for i in range(1, self.bit_max): if k & (1 << i): v = self.dub[i][v] return v def prod(self, v: int, k: int) -> S: if not self.built: self.build_doubling() res = self.node_val[v] for i in range(self.bit_max): if k & (1 << i): res = self.op(res, self.dp[i][v]) v = self.dub[i][v] return res N, K = map(int, input().split()) P = list(map(int, input().split())) edge_to = [(i + P[i]) % N for i in range(N)] node_val = list(range(N)) nxt_node_val = [i + P[i] for i in range(N)] op = lambda fr, to: to + fr // N * N F = FunctionalGraph(N, edge_to, node_val, nxt_node_val, op) for i in range(N): res = F.prod(i, K) print(res + 1)