QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#307011 | #7989. 三染色 | zhoukangyang | TL | 6ms | 4020kb | C++14 | 2.1kb | 2024-01-17 19:39:10 | 2024-01-17 19:39:11 |
Judging History
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;
auto pr = make_pair(col, val);
while(pr.second < 0) {
pr.second += 3;
for(auto&u : pr.first)if(u != mod)u += 3;
}
Add(nmp[1][pr], s.second.addk(i + j));
Add(nmp[0][pr], 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: 0ms
memory: 3572kb
input:
2 2 1 0 3 2
output:
1 2
result:
ok single line: '1 2'
Test #2:
score: 0
Accepted
time: 6ms
memory: 4020kb
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...