トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377) E,F,G問題メモ

def solve(n, k, ppp):
    ppp = [p - 1 for p in ppp]
    ans = [-1] * n
    for i in range(n):
        if ans[i] != -1:
            continue
        loop = [i]
        j = ppp[i]
        while j != i:
            loop.append(j)
            j = ppp[j]
        m = len(loop)
        kk = pow(2, k, m)
        for t in range(m):
            ans[loop[t]] = loop[(t + kk) % m]
    ans = [a + 1 for a in ans]
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ans = solve(n, k, ppp)
print(*ans)

from collections import defaultdict


def solve(n, m, queens):
    rows = set()
    cols = set()
    diag1 = set()
    diag2 = set()
    for i in range(m):
        x, y = queens[i]
        rows.add(x)
        cols.add(y)
        diag1.add(x + y)
        diag2.add(x - y)

    controlled = (len(rows) + len(cols)) * n
    for rc in diag1:
        if rc <= n + 1:
            controlled += rc - 1
        else:
            controlled += n * 2 - rc + 1
    for rc in diag2:
        controlled += n - abs(rc)

    duplicated = defaultdict(int)
    for r in rows:
        for c in cols:
            duplicated[r, c] += 1
        for rc in diag1:
            c = rc - r
            if 1 <= c <= n:
                duplicated[r, c] += 1
        for rc in diag2:
            c = r - rc
            if 1 <= c <= n:
                duplicated[r, c] += 1
    for c in cols:
        for rc in diag1:
            r = rc - c
            if 1 <= r <= n:
                duplicated[r, c] += 1
        for rc in diag2:
            r = rc + c
            if 1 <= r <= n:
                duplicated[r, c] += 1
    for rc1 in diag1:
        for rc2 in diag2:
            if rc1 % 2 != rc2 % 2:
                continue
            r = (rc1 + rc2) // 2
            c = rc1 - r
            if 1 <= r <= n and 1 <= c <= n:
                duplicated[r, c] += 1
    ans = n * n - controlled
    for cnt in duplicated.values():
        if cnt == 1:
            ans += 1
        elif cnt == 3:
            ans += 2
        else:
            ans += 3

    return ans


n, m = map(int, input().split())
queens = list(tuple(map(int, input().split())) for _ in range(m))
ans = solve(n, m, queens)
print(ans)

def solve(n, sss):
    class Node:
        def __init__(self):
            self.length = 1 << 60
            self.children = {}

        def __str__(self):
            s = [f'({self.length})']
            for c, node in self.children.items():
                node = str(node).split('\n')
                node[0] = f' |-{c}- {node[0]}'
                for i in range(1, len(node)):
                    node[i] = f' |    {node[i]}'
                s.extend(node)
            return '\n'.join(s)

    root = Node()
    buf = []
    for s in sss:
        t = ans = len(s)
        node = root
        for i, c in enumerate(s):
            if c not in node.children:
                node.children[c] = Node()
            node = node.children[c]
            ans = min(ans, t - i - 1 + node.length)
            node.length = min(node.length, t - i - 1)
        buf.append(ans)
    # print(root)

    return buf


n = int(input())
sss = [input() for _ in range(n)]
ans = solve(n, sss)
print('\n'.join(map(str, ans)))