QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706541#9563. 人间应又雪TheZone0 0ms0kbC++204.0kb2024-11-03 12:06:582024-11-03 12:06:59

Judging History

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

  • [2024-11-03 12:06:59]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-03 12:06:58]
  • 提交

answer

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
#define double long double

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

const int N = 15;
const int M = 2e5 + 5;

int n, S, flg;
int pw[N], op[3][3], top[3][3];

struct poly {
	
	ll a, b, c; // a + bx + cx ^ 2
	
	poly () : a(0), b(0), c(0) { }
	poly (ll _a, ll _b, ll _c) : a(_a), b(_b), c(_c) { }
	poly (ll x) : a(x), b(0), c(0) { }
	
	poly operator + (const poly &r) const {
		return poly(a + r.a, b + r.b, c + r.c);
	}
	
	poly operator - (const poly &r) const {
		return poly(a - r.a, b - r.b, c - r.c);
	}
	
	poly operator * (const poly &r) const {
		return poly(a * r.a + b * r.c + c * r.b, a * r.b + r.a * b + c * r.c, a * r.c + b * r.b + c * r.a);
	}
	
	ll val() {
		return a - b / 2 - c / 2;
	}
	
	bool operator == (const poly &r) const {
		return (a == r.a) && (b == r.b) && (c == r.c);
	}
	
};

const poly W[3] = { 
	poly(1, 0, 0), 
	poly(0, 1, 0), 
	poly(0, 0, 1)
};

poly f[N][M], g[N][M], h[N][M];
poly a[5][3], b[5][3], c[5][3];

void FWT(int d) {
	if (d == 1) {
		F (i, 0, 2) {
			h[d][i] = ll(0);
		}
		F (i, 0, 2) {
			F (j, 0, 2) {
				h[d][op[i][j]] = h[d][op[i][j]] + f[d][i] * g[d][j];
			}
		}
		return;
	}
	F (i, 0, pw[d] - 1) {
		h[d][i] = ll(0);
	}
	int k = pw[d - 1];
	F (t, 0, 4) {
		F (i, 0, k - 1) {
			f[d - 1][i] = f[d][i] * a[t][0] + f[d][i + k] * a[t][1] + f[d][i + 2 * k] * a[t][2];
			g[d - 1][i] = g[d][i] * b[t][0] + g[d][i + k] * b[t][1] + g[d][i + 2 * k] * b[t][2];
		}
		FWT(d - 1);
		F (i, 0, k - 1) {
			h[d][i] = h[d][i] + h[d - 1][i] * c[t][0];
			h[d][i + k] = h[d][i + k] + h[d - 1][i] * c[t][1];
			h[d][i + 2 * k] = h[d][i + 2 * k] + h[d - 1][i] * c[t][2];
		}
	}
}

bool chk(int o) {
	int fl = 0;
	F (A, 0, 26) {
		F (B, 0, 26) {
			F (C, 0, 26) {
				if (fl) {
					break;
				}
				int u[3], v[3], w[3];
				F (i, 0, 2) {
					u[i] = A / pw[i] % 3;
					v[i] = B / pw[i] % 3;
					w[i] = C / pw[i] % 3;
				}
				auto gt = [&](int i, int j) {
					if (!o) {
						return w[(u[i] + v[j]) % 3];
					} else {
						return w[max(u[i], v[j])];
					}
				};
				int df = 0;
				F (i, 0, 2) {
					F (j, 0, 2) {
						top[i][j] = gt(i, j);
						if (top[i][j] != op[i][j]) {
							df++;
						}
					}
				}
				if (df > 2) {
					continue;
				}
				fl = 1;
				F (i, 0, 2) {
					F (j, 0, 2) {
						if (!o) {
							a[i][j] = W[u[j] * i % 3];
							b[i][j] = W[v[j] * i % 3];
							c[i][w[j]] = c[i][w[j]] + W[(3 - i * j % 3) % 3];
						} else {
							a[i][j] = ll(u[j] <= i);
							b[i][j] = ll(v[j] <= i);
							if (i == j) {
								c[i][w[j]] = c[i][w[j]] + 1;
							}
							if (i + 1 == j) {
								c[i][w[j]] = c[i][w[j]] - 1;
							}
						}
					}
				}
				int t = 3;
				F (i, 0, 2) {
					F (j, 0, 2) {
						if (top[i][j] == op[i][j]) {
							continue;
						}
						a[t][i] = 1;
						b[t][j] = 1;
						c[t][top[i][j]] = (flg ? -1 : -3);
						c[t][op[i][j]] = (flg ? 1 : 3);
						t++;
					}
				}
			}
		}
	}
	return fl;
}

void solve() {
	F (i, 0, 2) {
		F (j, 0, 2) {
			cin >> op[i][j];
		}
	}
	cin >> n;
	pw[0] = 1;
	F (i, 1, 11) {
		pw[i] = pw[i - 1] * 3;
	}
	if (!chk(0)) {
		flg = 1;
		assert(chk(1));
	}
	S = pw[n];
	F (i, 0, S - 1) {
		cin >> f[n][i].a;
	}
	F (i, 0, S - 1) {
		cin >> g[n][i].a;
	}
	FWT(n);
	F (i, 0, S - 1) {
		cout << h[n][i].val() / (flg ? 1 : pw[n - 1]) << ' ';
	}
}

bool Med;
int main() {
//	 FIO("A");
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1000 1
9 8 0
8 5 2 1 6 4 5 1 5
9 8 0
1 7 3 2 0 8 5 1 0
8 9 0
3 8 7 3 2 4 9 9
8 9 0
8 3 9 3 9 8 3 4
9 10 0
0 9 5 5 4 3 6 10 5
8 8 0
3 5 1 6 8 4 2 5
8 9 0
5 2 3 8 1 4 2 9
10 8 0
2 8 2 3 1 7 0 1 5 1
8 9 0
1 0 4 9 9 5 7 2
9 10 0
3 4 0 10 0 9 6 7 0
8 9 0
4 8 4 4 0 4 2 3
9 8 0
0 5 2 3 1 0 4 0 0
10 10 0
3 ...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #3:

score: 0
Runtime Error

input:

1000 2
10 2 3
1 2 1 2 1 2 2 1 0 1
10 2 0
0 0 0 0 0 0 0 0 0 0
10 2 3
0 0 1 1 0 1 0 0 0 1
10 2 3
0 0 0 0 0 0 0 0 0 0
10 2 1
1 0 2 2 0 0 1 0 1 1
10 2 3
0 1 1 0 2 0 1 2 2 2
10 2 0
0 0 0 0 0 0 0 0 0 0
10 2 0
0 0 0 1 1 1 0 0 0 1
10 2 1
1 1 0 2 0 0 0 0 0 0
10 2 1
1 1 2 0 0 2 0 2 1 0
10 2 1
0 0 0 0 0 0 0 0 ...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #6:

score: 0
Runtime Error

input:

10 3
5 5 3
4 1 5 1 4
4 5 4
2 2 3 4
5 5 0
1 1 5 3 4
4 4 2
2 1 0 1
3 5 3
0 2 3
5 4 2
3 2 4 1 4
3 4 4
3 2 2
3 4 5
4 0 2
3 5 3
1 0 5
5 4 0
2 0 4 1 3

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Runtime Error

Test #33:

score: 0
Runtime Error

input:

5000 7
19 19 16
4 12 5 15 12 11 9 0 3 1 8 4 17 2 19 3 5 4 1
18 20 19
18 14 12 16 7 14 2 3 13 4 4 6 8 1 16 19 10 20
20 19 3
15 7 5 16 19 0 1 19 10 19 13 17 18 5 1 13 9 4 8 15
19 20 6
8 3 0 12 4 13 19 2 6 4 11 8 17 6 8 13 11 8 20
18 19 19
3 15 19 12 17 11 11 2 4 4 16 13 10 12 15 14 3 10
19 20 20
12 15...

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #6:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

0%

Subtask #10:

score: 0
Skipped

Dependency #2:

0%