Submission #69205220

---

Source Code Expand

// 可逆操作なので同値類に分けることができる。N=6程度で実験をすると同値類の性質として、
// (1) 和が0、和が1で先頭または末尾が1のものは孤立している。
// (2) それ以外のものは同じ和のものが1つのグループをなしている。
// と分かる。
//
//(2)は非自明で、十分性の証明はぱっと出てきませんね。
//和=1の区間同士のswapだけ考えれば十分なことは分かるんですが。

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <atcoder/dsu>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
using namespace atcoder;
typedef vector<int> Vec;
typedef vector<Vec> Mat;

void printVec(Vec a) {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i];
		if (i + 1 < a.size()) cout << " ";
	}
	cout << endl;
}

Mat generate_moves(Vec v) {
	int n = v.size();
	Mat vs;
	for (int a = 0; a < n; a++) {
		for (int b = a; b < n; b++) {
			for (int c = b + 1; c < n; c++) {
				for (int d = c; d < n; d++) {
					int i, s1 = 0, s2 = 0;
					for (i = a; i <= b; i++) s1 += v[i];
					for (i = c; i <= d; i++) s2 += v[i];
					if (s1 != s2) continue;

					Vec nv;
					for (i = 0; i < a; i++) nv.push_back(v[i]);
					for (i = c; i <= d; i++) nv.push_back(v[i]);
					for (i = b + 1; i < c; i++) nv.push_back(v[i]);
					for (i = a; i <= b; i++) nv.push_back(v[i]);
					for (i = d + 1; i < n; i++) nv.push_back(v[i]);
					vs.push_back(nv);
				}
			}
		}
	}
	return vs;
}

void test() {
		int n;
	cin >> n;

	Mat vecs;
	map<Vec, int> mp;

	int i, j;
	rep(i, (1 << n)) {
		Vec v;
		rep(j, n) v.push_back((i >> j) % 2);
		vecs.push_back(v);
		mp[v] = i;
	}
	
	dsu uf(1 << n);
	rep(i, (1 << n)) {
		Mat nvecs = generate_moves(vecs[i]);
		for (Vec nv: nvecs) {
			j = mp[nv];
			uf.merge(i, j);
		}
	}

	auto gs = uf.groups();
	for (auto g: gs) {
		cout << "g.size(): " << g.size() << endl;
		for (int id: g) {
			printVec(vecs[id]);
		}
		cout << "---" << endl;
	}

	cout << "gs.size(): " << gs.size() << endl;
}

bool solve(Vec a, Vec b) {
	int i;
	int n = a.size();

	if (a == b) return true;
	
	int sa = 0, sb = 0;
	rep(i, n) sa += a[i];
	rep(i, n) sb += b[i];
	if (sa != sb) return false;

	if (sa == 1 && (a[0] == 1 || a[n - 1] == 1)) return false;
	if (sb == 1 && (b[0] == 1 || b[n - 1] == 1)) return false;
	return true;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, i;
		cin >> n;
		Vec a(n), b(n);
		rep(i, n) cin >> a[i];
		rep(i, n) cin >> b[i];
		bool res = solve(a, b);
		if (res) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void printVec(Vec)’:
Main.cpp:21:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp:23:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 |                 if (i + 1 < a.size()) cout << " ";
      |                     ~~~~~~^~~~~~~~~~

Judge Result