結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2021-03-25 18:18:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 2,433 bytes |
コンパイル時間 | 1,393 ms |
コンパイル使用メモリ | 137,208 KB |
最終ジャッジ日時 | 2025-01-19 21:39:18 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <string> #include <map> #include <set> #include <stack> #include <tuple> #include <deque> #include <array> #include <numeric> #include <bitset> #include <iomanip> #include <cassert> #include <chrono> #include <random> #include <limits> #include <iterator> #include <functional> #include <sstream> #include <fstream> #include <complex> #include <cstring> #include <unordered_map> #include <unordered_set> using namespace std; using ll = long long; constexpr int INF = 1001001001; // constexpr int mod = 1000000007; constexpr int mod = 998244353; template<class T> inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template<class T> inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } struct UnionFind{ int sz; vector<int> par; vector<int> rank; UnionFind(int n) : sz(n) { par.resize(sz); rank.assign(sz, 0); for(int i = 0; i < sz; ++i){ par[i] = i; } } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } bool same(int x, int y){ return find(x) == find(y); } bool unite(int x, int y){ x = find(x), y = find(y); if(x == y) return false; if(rank[x] < rank[y]) par[x] = y; else{ par[y] = x; if(rank[x] == rank[y]) ++rank[x]; } return true; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> D(N), W(N); UnionFind uf(N); for(int i = 0; i < N; ++i){ cin >> D[i]; int j = (i + D[i]) % N, k = (i - D[i]) % N; if(k < 0) k += N; uf.unite(j, k); } vector<int> cnt(N); for(int i = 0; i < N; ++i){ cin >> W[i]; if(W[i] == 0) cnt[uf.find(i)] += 1; } vector<bool> ok(N); for(int i = 0; i < N; ++i){ int j = (i + D[i]) % N, k = (i - D[i]) % N; if(k < 0) k += N; if(j == k) ok[uf.find(j)] = true; } for(int i = 0; i < N; ++i){ if(uf.find(i) != i) continue; if(ok[i]) continue; if(cnt[i] % 2 == 1){ cout << "No\n"; return 0; } } cout << "Yes\n"; return 0; }