QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#117770 | #5576. Advertising ICPC | rania__ | WA | 48ms | 153108kb | C++14 | 3.7kb | 2023-07-02 05:53:12 | 2023-07-02 05:53:15 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 7, P1 = 31, P2 = 37, mod = 1e9 + 7;
int mul(int a, int b) {
return (1LL * a * b) % mod;
}
int add(int a, int b) {
a = (a + mod) % mod;
b = (b + mod) % mod;
return (a + b) % mod;
}
int fp(int b, int p) {
if (b == 1 or p == 0)
return 1;
int ret = fp(b, p >> 1);
ret = mul(ret, ret);
if (p & 1)
ret = mul(ret, b);
return ret;
}
ll modInv(ll n) {
return fp(n, mod - 2);
}
ll fact[N], inv[N];
void pre() {
fact[0] = inv[0] = 1;
for (ll i = 1; i < N; i++)
fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}
ll nCr(ll n, ll r) {
return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
ll nPr(ll n, ll r) {
return ((fact[n] * inv[n - r])) % mod;
}
int n, m;
char arr[255][255];
int dp[8*8+8][(1 << 8)+1][(1 << 8)+1][2][4];
// 1 -> i
// 2 -> p
// 3 -> c
int solve(int i, int j, int maski,int maskp, bool found,int lst) {
if (i == n)
return found;
if (j >= m) // row gded
return solve(i + 1, 0, maski,maskp,found,0);
int idx = (i * m + j);
int &ret = dp[idx][maski][maskp][found][lst];
if (~ret)
return ret;
ret = 0;
// mark as found
if ( j && maski&(1 << (j-1)) && (maskp & (1 << (j))) && lst == 3 && (arr[i][j]=='C' || arr[i][j] == '?'))
{
int nwi = maski;
int nwp = maskp;
nwi &= ~(1 << (j-1));
nwp &= ~(1 << (j-1));
nwi &= ~(1 << (j));
nwp &= ~(1 << (j));
ret = add(ret,solve(i,j+1,nwi,nwp,1,3));
}
else
{
//7ot c
// momken tb2a found
if ( j+1 < m && maski&(1 << (j)) && (maskp & (1 << (j+1))) && (arr[i][j]=='C' || arr[i][j] == '?'))
{
ret = add(ret,solve(i,j+1,maski,maskp,found,3));
}
//msh momken tb2a found
else if ((arr[i][j]=='C' || arr[i][j] == '?')){
int nwi = maski;
int nwp = maskp;
if (lst == 3)
{
nwi &= ~(1 << (j-1));
nwp &= ~(1 << (j-1));
}
nwi &= ~(1 << (j));
nwp &= ~(1 << (j));
ret = add ( ret, solve(i,j+1,nwi,nwp,found,3));
}
}
int nwi = maski;
int nwp = maskp;
if (lst == 3) {
nwi &= ~(1 << (j - 1));
nwp &= ~(1 << (j - 1));
}
nwi &= ~(1 << (j));
nwp &= ~(1 << (j));
// lw el ably c htfy el masken w abd2 3la ndafa
//7ot i
if ((arr[i][j]=='I' || arr[i][j] == '?'))
{
ret = add(ret, solve(i,j+1,nwi|(1 << j) , nwp , found , 1));
}
//7ot p
if ((arr[i][j]=='P' || arr[i][j] == '?'))
{
ret = add(ret, solve(i,j+1,nwi, nwp|(1 << j) , found , 2));
}
return ret;
}
void doWork() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m;++j) {
cin >> arr[j][i];
}
}
swap(m,n);
memset(dp, -1, sizeof dp);
cout << solve(0, 0, 0,0,0,0) << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("bisector.in","r",stdin);
// freopen("bisector.out","w",stdout);
int t = 1;
// cout << primes.size() << endl;
// cin >> t;
while (t--) {
doWork();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 152428kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 4ms
memory: 153028kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 48ms
memory: 153108kb
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????
output:
341329379
result:
wrong answer 1st lines differ - expected: '776529021', found: '341329379'