QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307009#7989. 三染色zhoukangyangTL 7ms4436kbC++142.0kb2024-01-17 19:36:212024-01-17 19:36:21

Judging History

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

  • [2024-01-17 19:36:21]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:4436kb
  • [2024-01-17 19:36:21]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1007, mod = 998244353;
int n, m;
int a[N][N];
struct node {
	int x, y;
	node(int X = 0, int Y = 0) {
		x = X;
		y = Y;
	}
	node addk(int k) {
		return node(x, (y + (ll)x * k) % mod);
	}
};
void Add(node &x, node y) {
	(x.x += y.x) %= mod, (x.y += y.y) %= mod;
}
map < pair < vi, int >, node > mp[2], nmp[2]; 
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	L(i, 0, n - 1) {
		L(j, 0, m - 1) {
			cin >> a[i][j];
		}
	}
	L(v, 0, 2) if(a[0][0] == 3 || a[0][0] == v) {
		vi fan(n);
		L(i, 0, n - 1) fan[i] = mod;
		fan[0] = v;
		L(o, 0, 1)Add(mp[o][make_pair(fan, v)], node(1, 0));
	}
	L(sum, 1, n + m - 2) {
		R(i, n - 1, 0) {
			int j = sum - i;
			L(o, 0, 1) 
				nmp[o].clear();
			L(o, 0, 1)
				for(auto&s : mp[o]) {
					auto col = s.first.first;
					int mn = s.first.second;
					if(j < 0 || j >= m) {
						col[i] = mod;
						Add(nmp[o][make_pair(col, mn)], s.second);
						continue;
					}
					int u = col[i], v = (i == 0 ? mod : col[i - 1]);
					if(u == mod)u = v;
					if(v == mod)v = u;
//					if(u == mod)cout<<"???"<<endl;
					L(val, max(u, v) - 1, min(u, v) + 1) { 
						int c = (val % 3 + 3) % 3;
						col[i] = val;
						if(a[i][j] != 3 && a[i][j] != c)continue;
						if(val < mn) {
							if(o == 1)continue;
							Add(nmp[1][make_pair(col, val)], s.second.addk(i + j));
							Add(nmp[0][make_pair(col, val)], s.second);
						} else {
							Add(nmp[o][make_pair(col, mn)], s.second);
						}
					}
				}
			swap(mp, nmp);
		}
	}
	node ans = 0; 
	for(auto&u : mp[1]) 
		Add(ans, u.second);
	cout << ans.x << ' ' << ans.y << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

input:

2 2
1 0
3 2

output:

1 2

result:

ok single line: '1 2'

Test #2:

score: 0
Accepted
time: 7ms
memory: 4436kb

input:

5 5
3 3 3 3 2
2 3 3 3 1
1 3 3 3 3
3 3 3 3 3
3 3 3 3 3

output:

50830224 170059345

result:

ok single line: '50830224 170059345'

Test #3:

score: -100
Time Limit Exceeded

input:

5 50
3 3 3 3 3 3 3 3 1 0 3 3 3 1 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 1 3 3 1 3 3 1 3 3 3 3 3 3 3 3 3 1 3 3 3 3 2 3 3 3 3 2 0 3 0 3 3 3 0 3 3 3 3 3 3 3 0 0 3 3 3 3
1 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 1 3 3 3 0 1 3 3 3 0 3 3 3 3 3 2 3 3 1 3 3 0 3 3 3...

output:


result: