QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117770#5576. Advertising ICPCrania__WA 48ms153108kbC++143.7kb2023-07-02 05:53:122023-07-02 05:53:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 05:53:15]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:153108kb
  • [2023-07-02 05:53:12]
  • 提交

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'