結果
問題 | No.2860 Heal Slimes |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:08:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 439 ms / 2,000 ms |
コード長 | 1,782 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 109,520 KB |
最終ジャッジ日時 | 2024-08-25 15:08:51 |
合計ジャッジ時間 | 13,087 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
from collections import defaultdictclass UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef solve():n, k, x = map(int,input().split())h = list(map(int,input().split()))if k == n:if max(h) == min(h):print("Yes")else:print("No")returnv = [h[i+1] - h[i] for i in range(n-1)]for i in range(n-1):if v[i] % x != 0:print("No")returnuf = UnionFind(n+1)for i in range(n-k+1):# h[i], ..., h[i+k-1]if i == 0:uf.union(i+k-1, n-1)elif i == n-k:uf.union(i-1, n)else:uf.union(i-1, i+k-1)dr = 0dg = 0mode = 0if uf.find(n-1) == uf.find(n):mode = 1t = defaultdict(int)for i in range(n-1):if uf.find(n-1) == uf.find(i):dr += v[i]elif uf.find(n) == uf.find(i):dg += v[i]else:t[uf.find(i)] += v[i]if t[uf.find(i)] > 0:print("No")returnif dr % x != 0:print("No")returnif dg % x != 0:print("No")returnif not mode:if dr < 0:print("No")returntmp = - drfor i in range(n-1):if uf.find(n-1) == uf.find(i):tmp += v[i]if tmp > 0:print("No")returnif dg > 0:print("No")returntmp = 0for i in range(n-1):if uf.find(n) == uf.find(i):tmp += v[i]if tmp > 0:print("No")returnfor i, c in t.items():if c != 0:print("No")returnprint("Yes")t = int(input())for _ in range(t):solve()