QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241453#1286. Ternary String Countingle6666WA 0ms3924kbC++143.2kb2023-11-06 07:51:572023-11-06 07:51:58

Judging History

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

  • [2023-11-06 07:51:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3924kb
  • [2023-11-06 07:51:57]
  • 提交

answer

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

const ll MOD = 1e9 + 7;
const int MAXN = 5e3 + 5;
int n, m, lj[MAXN], rj[MAXN], lk[MAXN], rk[MAXN];
struct Limit { int l, r, x; } lim[MAXN];
int nl[MAXN], nr[MAXN];
struct LL {
	ll num = 0;
	LL operator+ (LL other) { return { (num + other.num) % MOD }; }
	LL operator+ (ll k) { return { (num + k) % MOD }; }
	LL operator- (LL other) { return { (num - other.num + MOD) % MOD }; }
	void operator+= (LL other) { *this = *this + other; }
	void operator-= (LL other) { *this = *this - other; }
	LL operator= (ll k) { num = k; return *this; }
};
LL f[MAXN][MAXN], hang[MAXN], lie[MAXN];

void test() {
	for (int i = 0 ; i <= n; i++) {
		for (int j = 0; j <= n; j++) printf("%lld ", f[i][j].num);
		printf("\n");
	}
	printf("\n");
}

void del(int x, int y) {
//	printf("del(%d, %d)\n", x, y);
	if (x || y) hang[x] -= f[x][y], lie[y] -= f[x][y], f[x][y] = 0;
	else if (!x && !y) f[0][0] = 0;
//	else if (!y) lie[0] -= f[x][0], f[x][0] = 0;
}

bool in(int x, int y) { return nl[x] <= y && y <= nr[x]; }

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) scanf("%d%d%d", &lim[i].l, &lim[i].r, &lim[i].x);
		for (int i = 0; i <= n; i++) lj[i] = lk[i] = nl[i] = 0, rj[i] = rk[i] = nr[i] = n;
		for (int i = 0; i <= n; i++) {
			hang[i] = lie[i] = 0;
			for (int j = 0; j <= n; j++)
				f[i][j] = 0;
		}
		for (int i = 1; i <= m; i++) {
			auto [l, r, x] = lim[i];
			rj[r] = max(rj[r], 1), lj[r] = max(lj[r], 1), rk[r] = max(rk[r], 1), lk[r] = max(lk[r], 1);
			if (x == 1) rj[r] = min(rj[r], l - 1);
			else if (x == 2) lj[r] = max(lj[r], l), rk[r] = min(rk[r], l - 1);
			else lk[r] = max(lk[r], l);
		}
//		bool flag = false;
//		for (int i = 1; i <= n; i++)
//			if (lj[i] > rj[i] || lk[i] > rk[i])
//				flag = true;
//		if (flag) { printf("0\n"); continue; }
//		f[0][0] = hang[0] = lie[0] = 1;
		f[0][0] = 1;
		for (int i = 2; i <= n; i++) {
			if (in(i - 1, 0)) f[i - 1][0] = lie[0] + 1, hang[i - 1] += f[i - 1][0], lie[0] += f[i - 1][0];
			for (int j = 1; j < i - 1; j++) /*if (in(i - 1, j))*/ f[i - 1][j] = hang[j] + lie[j];
			for (int j = 1; j < i - 1; j++) hang[i - 1] += f[i - 1][j], lie[j] += f[i - 1][j];
			for (int j = 0; j < lj[i]; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
			for (int j = lj[i]; j <= rj[i]; j++) {
				for ( ; nl[j] <= nr[j] && nl[j] < lk[i]; nl[j]++)
					del(j, nl[j]);
				for ( ; nl[j] <= nr[j] && rk[i] < nr[j]; nr[j]--)
					del(j, nr[j]);
			}
			for (int j = rj[i] + 1; j <= n; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
			test();
		}
		ll ans = 0;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				if (i == 0 && j == 0) ans = (ans + f[i][j].num * 3) % MOD;
				else if (i == 0 || j == 0) ans = (ans + f[i][j].num * 6) % MOD;
				else ans = (ans + f[i][j].num * 6) % MOD;
		printf("%lld\n", ans);
//		for (int i = 1; i <= n; i++) {
//			printf("%d %d %d %d\n", lk[i], rk[i], lj[i], rj[i]);
//		}
	}
	return 0;
}

/*

4
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
10 3
9 10 2
3 6 3
1 9 1
10 4
6 6 1
9 10 2
4 8 3
4 10 3

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

3
1 0 0 
1 0 0 
0 0 0 

9
1 0 0 0 
1 0 0 0 
0 0 0 0 
0 0 0 0 

1 0 0 0 
1 0 0 0 
2 1 0 0 
0 0 0 0 

27
1 0 0 0 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 0 0 0 0 
...

result:

wrong answer 2nd words differ - expected: '9', found: '1'