結果
問題 | No.2860 Heal Slimes |
ユーザー | shobonvip |
提出日時 | 2024-08-25 15:02:07 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,713 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 109,600 KB |
最終ジャッジ日時 | 2024-08-25 15:02:21 |
合計ジャッジ時間 | 13,811 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 436 ms
80,396 KB |
testcase_06 | AC | 396 ms
80,252 KB |
testcase_07 | AC | 444 ms
79,260 KB |
testcase_08 | AC | 427 ms
80,556 KB |
testcase_09 | AC | 408 ms
80,116 KB |
testcase_10 | AC | 102 ms
76,360 KB |
testcase_11 | AC | 108 ms
76,508 KB |
testcase_12 | AC | 112 ms
76,528 KB |
testcase_13 | AC | 107 ms
76,204 KB |
testcase_14 | AC | 102 ms
76,136 KB |
testcase_15 | AC | 153 ms
77,228 KB |
testcase_16 | AC | 159 ms
77,308 KB |
testcase_17 | AC | 155 ms
77,348 KB |
testcase_18 | AC | 158 ms
77,096 KB |
testcase_19 | AC | 157 ms
77,164 KB |
testcase_20 | AC | 130 ms
102,940 KB |
testcase_21 | AC | 138 ms
103,176 KB |
testcase_22 | AC | 122 ms
92,180 KB |
testcase_23 | AC | 140 ms
103,124 KB |
testcase_24 | AC | 151 ms
100,808 KB |
testcase_25 | AC | 94 ms
99,192 KB |
testcase_26 | AC | 79 ms
88,408 KB |
testcase_27 | AC | 104 ms
102,840 KB |
testcase_28 | AC | 113 ms
99,588 KB |
testcase_29 | AC | 106 ms
99,672 KB |
testcase_30 | AC | 106 ms
109,448 KB |
testcase_31 | AC | 112 ms
102,060 KB |
testcase_32 | AC | 115 ms
101,692 KB |
testcase_33 | AC | 107 ms
109,236 KB |
testcase_34 | AC | 119 ms
103,172 KB |
testcase_35 | AC | 116 ms
101,368 KB |
testcase_36 | AC | 109 ms
109,048 KB |
testcase_37 | AC | 116 ms
106,876 KB |
testcase_38 | AC | 110 ms
109,600 KB |
testcase_39 | AC | 119 ms
106,636 KB |
testcase_40 | AC | 162 ms
104,984 KB |
testcase_41 | AC | 161 ms
103,692 KB |
testcase_42 | AC | 161 ms
103,692 KB |
testcase_43 | AC | 168 ms
106,400 KB |
testcase_44 | AC | 164 ms
103,584 KB |
testcase_45 | AC | 149 ms
103,320 KB |
testcase_46 | AC | 172 ms
103,440 KB |
testcase_47 | AC | 149 ms
103,460 KB |
testcase_48 | AC | 164 ms
103,444 KB |
testcase_49 | AC | 142 ms
103,712 KB |
testcase_50 | AC | 165 ms
107,156 KB |
testcase_51 | AC | 162 ms
103,692 KB |
testcase_52 | AC | 162 ms
103,704 KB |
testcase_53 | AC | 151 ms
103,320 KB |
testcase_54 | AC | 165 ms
106,632 KB |
testcase_55 | AC | 144 ms
103,328 KB |
testcase_56 | AC | 168 ms
107,680 KB |
testcase_57 | AC | 164 ms
105,500 KB |
testcase_58 | AC | 162 ms
103,700 KB |
testcase_59 | AC | 143 ms
103,560 KB |
ソースコード
from collections import defaultdict class UnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: 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: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def 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") return v = [h[i+1] - h[i] for i in range(n-1)] uf = 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 = 0 dg = 0 mode = 0 if uf.find(n-1) == uf.find(n): mode = 1 t = 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") return if dr % x != 0: print("No") return if dg % x != 0: print("No") return if not mode: if dr < 0: print("No") return tmp = - dr for i in range(n-1): if uf.find(n-1) == uf.find(i): tmp += v[i] if tmp > 0: print("No") return if dg > 0: print("No") return tmp = 0 for i in range(n-1): if uf.find(n) == uf.find(i): tmp += v[i] if tmp > 0: print("No") return for i, c in t.items(): if c != 0: print("No") return print("Yes") t = int(input()) for _ in range(t): solve()