QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #95089 | #5576. Advertising ICPC | Nicolas125841 | WA | 32ms | 5028kb | C++14 | 3.0kb | 2023-04-09 02:24:34 | 2023-04-09 02:24:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
vector<vector<ll>> dp(19683, vector<ll>(2, 0)), dpn(19683, vector<ll>(2, 0));
char mp[8][8];
char conv(int i){
if(i == 0)
return 'C';
else if(i == 1)
return 'I';
else
return 'P';
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
int m_max = pow(3, m+1);
int m_jmp = pow(3, m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> mp[i][j];
for(int i = 0; i < m_max; i++){
int ti = i, iv;
bool good = true;
iv = ti%3;
if(mp[1][0] != '?' && conv(ti) != mp[1][0])
good = false;
ti /= 3;
for(int j = m-1; j >= 0; j--){
iv = ti%3;
if(mp[0][j] != '?' && conv(iv) != mp[0][j])
good = false;
ti /= 3;
}
if(good)
dp[i][0] = 1;
}
for(int i = 1; i < n; i++){
for(int j = ((i == 1) ? 1 : 0); j < m; j++){
for(int k = 0; k < m_max; k++){
if(mp[i][j] == '?' || mp[i][j] == 'C'){
int msk = (3*k) % m_max;
if(j > 0 && (k/m_jmp)%3 == 1 && (msk/m_jmp)%3 == 0 && k%3 == 2){
dpn[msk][1] += dp[k][0] + dp[k][1];
dpn[msk][1] %= mod;
}else{
dpn[msk][0] += dp[k][0];
dpn[msk][1] += dp[k][1];
dpn[msk][0] %= mod;
dpn[msk][1] %= mod;
}
}
if(mp[i][j] == '?' || mp[i][j] == 'I'){
int msk = (3*k + 1) % m_max;
dpn[msk][0] += dp[k][0];
dpn[msk][1] += dp[k][1];
dpn[msk][0] %= mod;
dpn[msk][1] %= mod;
}
if(mp[i][j] == '?' || mp[i][j] == 'P'){
int msk = (3*k + 2) % m_max;
dpn[msk][0] += dp[k][0];
dpn[msk][1] += dp[k][1];
dpn[msk][0] %= mod;
dpn[msk][1] %= mod;
}
}
ll tans = 0;
ll ttmp = 0;
for(int k = 0; k < m_max; k++){
ttmp += dp[k][0] = dpn[k][0] % mod;
tans += dp[k][1] = dpn[k][1] % mod;
dpn[k][0] = dpn[k][1] = 0;
tans %= mod;
ttmp %= mod;
//if(i == 3 && j == 3)
// cout << ttmp << " " << dp[k][0] << " " << k << "\n";
}
// cout << i << " " << j << " " << tans << " " << ttmp << "\n";
}
}
ll ans = 0;
for(int i = 0; i < m_max; i++){
ans += dp[i][1];
ans %= mod;
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 4936kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4932kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 32ms
memory: 5008kb
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????
output:
776529021
result:
ok single line: '776529021'
Test #4:
score: 0
Accepted
time: 4ms
memory: 4940kb
input:
2 2 ?? ??
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 4940kb
input:
2 2 CP CI
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 4ms
memory: 4964kb
input:
2 2 IP CC
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4984kb
input:
2 2 PI CC
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 4ms
memory: 5028kb
input:
2 2 CI CP
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 8ms
memory: 4936kb
input:
2 8 ???P???? ???P??P?
output:
115443
result:
ok single line: '115443'
Test #10:
score: 0
Accepted
time: 7ms
memory: 5024kb
input:
2 8 IC???C?? ?I?IC?I?
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Wrong Answer
time: 4ms
memory: 4968kb
input:
2 8 ?????P?? I???C??I
output:
0
result:
wrong answer 1st lines differ - expected: '32562', found: '0'