QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683367#6432. Puzzle in InazumaAndycraftWA 0ms3756kbC++204.1kb2024-10-27 20:33:292024-10-27 20:33:29

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 20:33:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3756kb
  • [2024-10-27 20:33:29]
  • 提交

answer

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
template <class T> using Arr = std::vector<T>;
typedef long long LL;
#if 1
#ifdef assert
#undef assert
#endif
#define assert(x) ({ if (!(x)) printf("%s\n", #x); exit(0); })
#endif

const int MAXN = 105;
int g[MAXN][MAXN], h[MAXN][MAXN];
int n;

void dfs(int now, int dep, const int &m, Arr<Arr<int>> &v) {
	static Arr<int> buf;
	if (dep == 4) {
		v.push_back(buf);
		return;
	}
	for (int i = now; i <= m; ++i) {
		buf.push_back(i);
		dfs(i + 1, dep + 1, m, v);
		buf.pop_back();
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	LL sum = 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> g[i][j];
			g[j][i] = g[i][j];
			sum += g[i][j];
		}
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> h[i][j];
			h[j][i] = h[i][j];
			sum -= h[i][j];
		}
	if (sum != 0)
		return puts("-1"), 0;
	Arr<Arr<int>> ans;
	auto act = [&](int a, int b, int c, int d, int x) {
		assert(a != b && a != c && a != d && b != c && b != d && c != d);
		ans.push_back({a, b, c, d, x});
		g[a][b] += x;
		g[a][c] += x;
		g[a][d] += x;
		g[b][c] -= x;
		g[c][d] -= x;
		g[b][d] -= x;

		g[b][a] += x;
		g[c][a] += x;
		g[d][a] += x;
		g[c][b] -= x;
		g[d][c] -= x;
		g[d][b] -= x;
	};
	auto mex = [&](Arr<int> v) { std::ranges::sort(v); v.erase(std::unique(v.begin(), v.end()), v.end()); for (int i = 0; i < (int)v.size(); ++i) if (v[i] != i) return i; return (int)v.size(); };
	auto cross_legacy = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		act(a, b, c, d, x / 2);
		act(b, a, c, d, x / 2);
	};
	auto cross = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		int u = mex({a - 1, b - 1, c - 1, d - 1}) + 1;
		int v = mex({a - 1, b - 1, c - 1, d - 1, u - 1}) + 1;
		cross_legacy(a, b, u, v, x);
		cross_legacy(u, v, c, d, x);
	};
	for (int i = n; i > 6; --i) {
		Arr<int> tp;
		for (int j = 1; j < i; ++j)
			if ((g[j][i] ^ h[j][i]) & 1)
				tp.push_back(j);
		int m = (int)tp.size();
		int j;
		for (j = 0; j + 3 <= m; j += 3)
			act(i, tp[j], tp[j + 1], tp[j + 2], 1);
		j -= 3;
		if (m == j + 1) {
			int u = mex({tp[j] - 1}) + 1;
			int v = mex({tp[j] - 1, u - 1}) + 1;
			int w = mex({tp[j] - 1, u - 1, v - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j], u, w, 1);
			act(i, tp[j], v, w, 1);
		} else if (m == j + 2) {
			int u = mex({tp[j] - 1, tp[j + 1] - 1}) + 1;
			int v = mex({tp[j] - 1, tp[j + 1] - 1, u - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j + 1], u, v, 1);
		} else
			assert(m == j);
	}

	int m = std::min(n, 6);
	Arr<Arr<int>> ch;
	dfs(1, 0, m, ch);
	int K = (int)ch.size();
	bool success = false;
	for (int S = 0; S < (1 << K); ++S) {
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;

		bool fail = false;
		for (int i = 1; i < m; ++i)
			for (int j = i + 1; j <= m; ++j)
				if ((g[i][j] ^ h[i][j]) & 1) {
					fail = true;
					break;
				}
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;
		if (!fail) {
			success = true;
			for (int i = 0; i < K; ++i)
				if (S & (1 << i))
					act(ch[i][0], ch[i][1], ch[i][2], ch[i][3], 1);
			break;
		}
	}
	if (!success)
		return puts("-1"), 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			assert(~(g[i][j] ^ h[i][j]) & 1);
	if (n >= 6) {
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					assert(i != 2 || j != 1);
					int u = 1, v = 2;
					cross(i, j, u, v, h[i][j] - g[i][j]);
				}
	} else
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					// assert(i != 2 || j != 1);
					int u = mex({i - 1, j - 1}) + 1;
					int v = mex({i - 1, j - 1, u - 1}) + 1;
					cross_legacy(i, j, u, v, h[i][j] - g[i][j]);
				}
	// for (int i = 1; i < n; ++i)
	// 	for (int j = i + 1; j <= n; ++j)
	// 		assert(g[i][j] == h[i][j]);
	printf("%lu\n", ans.size());
	for (auto v : ans)
		printf("%d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3756kb

input:

4
0 1 1
0 0
1
1 0 0
1 1
0

output:


result:

wrong output format Unexpected end of file - int32 expected