結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2016-09-05 15:19:51 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,300 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 116,980 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 04:10:44 |
合計ジャッジ時間 | 1,928 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import std.algorithm, std.array, std.container, std.range, std.bitmanip;import std.numeric, std.math, std.bigint, std.random, core.bitop;import std.string, std.conv, std.stdio, std.typecons;class UnionFind {int[] par;this(int n) {par = new int[](n);par[] = -1;}int find(int i) {if (par[i] < 0) {return i;} else {par[i] = find(par[i]);return par[i];}}void unite(int i, int j) {auto pi = find(i), pj = find(j);if (pi != pj) par[pj] = pi;}}void main(){auto n = readln.chomp.to!int;auto di = readln.split.map!(to!int);auto wi = readln.split.map!(a => a.to!int == 0 ? false : true);auto uf = new UnionFind(n);int[] isolateds;foreach (i; 0..n) {auto j1 = (i + di[i]) % n;auto j2 = (i - (di[i] % n) + n) % n;if (j1 == j2)isolateds ~= j1;elseuf.unite(j1, j2);}int[][int] h;foreach (i; 0..n)h[uf.find(i)] ~= i;auto r = true;foreach (pi; h.byValue) {if (pi.length == 1) {if (!wi[pi.front]) {r = false;break;}} else {auto c = pi.count!(p => !wi[p]);if (c % 2 != 0 && !isolateds.any!(a => pi.canFind(a))) {r = false;break;}}}writeln(r ? "Yes" : "No");}