結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2015-08-02 09:58:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 3,613 bytes |
コンパイル時間 | 1,678 ms |
コンパイル使用メモリ | 168,288 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 00:46:05 |
合計ジャッジ時間 | 2,355 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class UFTree {std::vector<int> par_;std::vector<int> rank_;public:UFTree(int N) { init(N); }UFTree() {}~UFTree() {}void init(int N) {par_.resize(N);rank_.resize(N, 0);for (int i = 0; i < N; ++i)par_[i] = i;}int find(int x) {if ( par_[x] == x )return x;elsereturn ( par_[x] = find(par_[x]));}void unite(int x, int y) {x = find(x);y = find(y);if ( x == y )return;if ( rank_[x] < rank_[y] )par_[x] = y;else{par_[y] = x;if ( rank_[x] == rank_[y] )++rank_[x];}}bool same(int x, int y) {return (find(x) == find(y));}int operator[](size_t i) { return find(i); }};class BoredomOfSavingsBox {public:void solve(void) {int N;cin>>N;//// 同時にひっくり返せるものを一つのグループとして考える。//// 0,1,1,0,1,...//// これは適当にコインをひっくりかえすことで//// A. 1,1,1,...,1,1// B. 1,1,1,,..,1,0//// のどちらかのケースに帰着できる// (以下のように反転していけるから// 0,1,* -> 1,0,*// 0,0,* -> 1,1,*// 1,0,1 -> 1,1,0// 1,0,0 -> 1,1,1// )//// 一度に二個のコインをひっくり返すので// 裏になっているコインの数の偶奇は変化しない。// よって初期状態の裏のコインの数が奇数のときは全て表にはできない。//// ただし1個だけコインをひっくり返せる場合はそれで帳尻があうので全て表にできる。//UFTree uft(N);vector<bool> one(N,false);REP(i,N){int d;cin>>d;int l = (1000*N+i-d)%N;int r = (d+i)%N;// 同時にひっくり返せるものを統合するuft.unite(l,r);if (l == r)one[i] = true;}// 各連結成分での偶奇チェックvector<int> num(N,0);REP(i,N){int w;cin>>w;num[uft[i]] += (w==0); // 裏になっているコインの数を数える// 各 one の結果を連結成分に適用if (one[i])one[uft[i]] = true;}// 各連結成分ごとにチェックREP(i,N){if (uft[i] != i) // 連結成分ごとにチェックcontinue;if (num[uft[i]]%2 && !one[uft[i]]){cout<<"No"<<endl;return;}}cout<<"Yes"<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new BoredomOfSavingsBox();obj->solve();delete obj;return 0;}#endif