結果
問題 |
No.3171 Color Restoration
|
ユーザー |
![]() |
提出日時 | 2025-06-06 21:24:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 3,932 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 52,736 KB |
最終ジャッジ日時 | 2025-06-06 21:24:47 |
合計ジャッジ時間 | 2,583 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
def distinct_permutations(iterable, r=None): """Yield successive distinct permutations of the elements in *iterable*. >>> sorted(distinct_permutations([1, 0, 1])) [(0, 1, 1), (1, 0, 1), (1, 1, 0)] Equivalent to ``set(permutations(iterable))``, except duplicates are not generated and thrown away. For larger input sequences this is much more efficient. Duplicate permutations arise when there are duplicated elements in the input iterable. The number of items returned is `n! / (x_1! * x_2! * ... * x_n!)`, where `n` is the total number of items input, and each `x_i` is the count of a distinct item in the input sequence. If *r* is given, only the *r*-length permutations are yielded. >>> sorted(distinct_permutations([1, 0, 1], r=2)) [(0, 1), (1, 0), (1, 1)] >>> sorted(distinct_permutations(range(3), r=2)) [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)] """ # Algorithm: https://w.wiki/Qai def _full(A): while True: # Yield the permutation we have yield tuple(A) # Find the largest index i such that A[i] < A[i + 1] for i in range(size - 2, -1, -1): if A[i] < A[i + 1]: break # If no such index exists, this permutation is the last one else: return # Find the largest index j greater than j such that A[i] < A[j] for j in range(size - 1, i, -1): if A[i] < A[j]: break # Swap the value of A[i] with that of A[j], then reverse the # sequence from A[i + 1] to form the new permutation A[i], A[j] = A[j], A[i] A[i + 1 :] = A[: i - size : -1] # A[i + 1:][::-1] # Algorithm: modified from the above def _partial(A, r): # Split A into the first r items and the last r items head, tail = A[:r], A[r:] right_head_indexes = range(r - 1, -1, -1) left_tail_indexes = range(len(tail)) while True: # Yield the permutation we have yield tuple(head) # Starting from the right, find the first index of the head with # value smaller than the maximum value of the tail - call it i. pivot = tail[-1] for i in right_head_indexes: if head[i] < pivot: break pivot = head[i] else: return # Starting from the left, find the first value of the tail # with a value greater than head[i] and swap. for j in left_tail_indexes: if tail[j] > head[i]: head[i], tail[j] = tail[j], head[i] break # If we didn't find one, start from the right and find the first # index of the head with a value greater than head[i] and swap. else: for j in right_head_indexes: if head[j] > head[i]: head[i], head[j] = head[j], head[i] break # Reverse head[i + 1:] and swap it with tail[:r - (i + 1)] tail += head[: i - r : -1] # head[i + 1:][::-1] i += 1 head[i:], tail[:] = tail[: r - i], tail[r - i :] items = sorted(iterable) size = len(items) if r is None: r = size if 0 < r <= size: return _full(items) if (r == size) else _partial(items, r) return iter(() if r else ((),)) S = input().split() color = [["gray","brown","green","cyan","blue","yellow","orange","red"], ["gray","green","blue","yellow","red"], ["gray","green","cyan","blue","violet","orange","red"]] count = 0 for a,b,c in distinct_permutations(S): count += (a in color[0] and b in color[1] and c in color[2]) print("Yes" if count == 1 else "No")