#252090 (C++14) No.74 貯金箱の退屈

提出ソース

結果

問題	No.74 貯金箱の退屈
ユーザー	Yang33
提出日時	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,778 ms
コンパイル使用メモリ	178,680 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-27 04:01:47
合計ジャッジ時間	2,817 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	4 ms 6,940 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	3 ms 6,944 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	3 ms 6,940 KB
testcase_12	AC	3 ms 6,944 KB
testcase_13	AC	4 ms 6,940 KB
testcase_14	AC	6 ms 6,944 KB
testcase_15	AC	3 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	3 ms 6,944 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	3 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	3 ms 6,940 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	4 ms 6,944 KB
testcase_27	AC	4 ms 6,944 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	3 ms 6,944 KB
testcase_30	AC	3 ms 6,944 KB
testcase_31	AC	3 ms 6,940 KB
testcase_32	AC	3 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}