Submission #20176791

---

Source Code Expand

import sys

def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x

def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

def Z_inv(Z):
    N = len(Z)
    EQ = []
    NEQ = []
    if Z[0] != N:
        return False
    i, j = 1, 0
    while i < N:
        while i + j < N:
            if Z[i] != j:
                EQ.append((j, i + j))
                j += 1
            else:
                NEQ.append((j, i + j))
                break
        if Z[i] != j:
            return False
        if not j:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            if Z[i + k] != Z[k]:
                return False
            k += 1
        i += k
        j -= k
    root = list(range(N))
    size = [0]*N
    uf = (root, size)
    for i, j in EQ:
        merge(uf, i, j)
    for i, j in NEQ:
        if find_root(uf, i) == find_root(uf, j):
            return False
    return True

print('Yes'if Z_inv(list(map(int,open(0).read().split()))[:0:-1])else'No')

Submission Info

Judge Result