結果

問題 No.74 貯金箱の退屈
ユーザー Yang33Yang33
提出日時 2018-04-16 17:16:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 5,501 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 174,508 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-09 10:54:09
合計ジャッジ時間 3,668 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 6 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 3 ms
4,376 KB
testcase_27 AC 3 ms
4,380 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 4 ms
4,376 KB
testcase_32 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/04/16  Problem: yukicoder 074  / Link: http://yukicoder.me/problems/no/074  ----- */
/* ------問題------

貯金箱くんはとても退屈していました。
そこで自分が持っている硬貨で遊ぶことにしました。

まず自分の持っている硬貨を床にばらまき、そこから N 枚硬貨を選び円形に並べます。
次に N 枚の硬貨から適当に1枚選びます。選んだ硬貨の額面を D 円としたとき、選んだ硬貨から時計回りに D 個先の硬貨と、反時計回りに D 個先の硬貨をひっくり返します。
ただし時計回りでも反時計回りでも同じ硬貨だった場合はその硬貨を1回だけひっくり返します。
貯金箱くんは、この操作を繰り返しすべての硬貨を表向きにしたいです。

硬貨の並び、額面、最初の裏表が与えられるのですべての硬貨を表向きにできるか判定してください。
ただし同じ硬貨を複数回選んでもよいとします。

-----問題ここまで----- */
/* -----解説等-----

無限時間解けてア

----解説ここまで---- */
struct UnionFind {
	vector<int> data;
	UnionFind(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};



long long extgcd(long long a, long long b, long long &x, long long &y) {
	long long d = a;
	if (b != 0) {
		d = extgcd(b, a%b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

long long mod_inverse(long long a, long long m) {
	long long x, y;
	extgcd(a, m, x, y);
	return (m + x%m) % m;
}


// A[n*p] * X[p*m] = B[n*m]
template<class T = int>
int gaussian_elimination_with_mod(vector<vector<T>>& A, vector<vector<T>>& B, int n, int p, int m, const T mod) {
	int R = max(n, p); int C = p + m;
	vector<vector<T>> V(R, vector<T>(C, 0));
	for (int i = 0; i<n; i++)
		for (int j = 0; j<p; j++) V[i][j] = A[i][j];
	for (int i = 0; i<n; i++)
		for (int j = 0; j<m; j++) V[i][j + p] = B[i][j];


	int rank = 0;
	int row = 0;

	vector<int> left(R, -1);

	//foward
	for (int col = 0; col<C && row<R; col++) {
		//pivot
		T val = abs(V[row][col]);
		int pivot = row;
		for (int j = row + 1; j<R; j++) {
			if (val < abs(V[j][col])) {
				val = abs(V[j][col]);
				pivot = j;
			}
		}
		if (pivot != row) swap(V[row], V[pivot]);

		if (val == 0) continue;

		T inv = mod_inverse(val, mod);
		for (int j = row + 1; j<R; j++) {
			T c = (V[j][col] * inv + mod) % mod;
			for (int k = col; k<p + m; k++) V[j][k] = ((V[j][k] - V[row][k] * c) % mod + mod) % mod;
		}

		left[row] = col;
		row++;
		rank++;
	}

	//backward
	for (int i = R - 1; i >= 0; i--) {
		bool zero = true;
		bool valid = true;
		for (int col = 0; col<p; col++) if (V[i][col] != 0) zero = false;
		for (int col = p; zero && col<C; col++) if (V[i][col] != 0) valid = false;

		if (valid == false) return -1;	//no solution

		if (left[i] == -1) continue;

		T inv = mod_inverse(V[i][left[i]], mod);
		for (int j = left[i]; j<C; j++) V[i][j] = (V[i][j] * inv) % mod;

		for (int j = i - 1; j >= 0; j--) {
			for (int k = 0; k<C; k++) {
				V[j][k] = ((V[j][k] - V[j][i] * V[i][k]) % mod + mod) % mod;
			}
		}
	}
	//return V;
	return rank;
}

void solve() {
	LL N; cin >> N;
	VL D(N), W(N);
	FOR(i, 0, N)cin >> D[i];
	FOR(i, 0, N)cin >> W[i];
	VVI A(N, VI(N, 0));
	FOR(i, 0, N) {
		int r = (i + D[i]) % N;
		int l = (i - D[i] + N * 1000) % N;
		A[r][i] = A[l][i] = 1;
	}
	VVI B(N, VI(1, 0));
	FOR(i, 0, N) {
		B[i][0] = !W[i];
	}

	int ans = gaussian_elimination_with_mod(A, B, N, N, 1, 2);
	cout << (ans == -1 ? "No" : "Yes") << endl;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	solve();
	return 0;

	LL N; cin >> N;
	UnionFind uf(N);
	VL D(N), W(N);
	VI self(N, 0);
	FOR(i, 0, N) {
		cin >> D[i];
		int r = (i + D[i]) % N;
		int l = (i - D[i] + N * 1000) % N;
		if (r == l)self[r] = 1;
		uf.unionSet(r, l);
	}
	VI groupOK(N, 0);
	FOR(i, 0, N) {
		if (self[i])groupOK[uf.root(i)] = 1;
	}
	VI groupSIZE(N, 0);
	FOR(i, 0, N) {
		int w; cin >> w;//0:裏
		if (w == 0) {
			groupSIZE[uf.root(i)]++;
		}
	}
	FOR(i, 0, N) {
		if (uf.root(i) == i && groupSIZE[i] % 2 == 1 && groupOK[i] == 0) {
			cout << "No" << endl; return 0;
		}
	}
	cout << "Yes" << "\n";
	return 0;
}
0