Submission #60255

#	Time	Username	Problem	Language	Result	Execution time	Memory
60255		Benq	Bowling (BOI15_bow)	C++11	100 / 100	535 ms	9384 KiB

bow

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


struct hsh {
    size_t operator()(const pi& k) const {
        return (ll)MOD*k.f+k.s; // bad, but you get the point
    }
};

int q, n, num[10], ret;
ll m[2][3][301][301], M[2][3][301][301];
string tmp[10];

string gen(vi nex) {
    int lst = -1;
    string res;
    for (int i: nex) {
        if (i == -1) res += '-';
        else if (lst != -1 && i+lst == 10) {
            res += '/';
            lst = -1;
        } else if (i == 10) res += 'x';
        else {
            if (lst == -1) lst = 0;
            res += char('0'+i);
            lst += i;
        }
    }
    return res;
}

bool match(string bad, vi nex) {
    string t = gen(nex);
    F0R(i,sz(bad)) if (bad[i] != '?' && bad[i] != t[i]) return 0;
    return 1;
}


void tri(int a, int b, int c, int d, int x, vi y) {
    ll val = m[a][b][c][d];
    int cur = d;
    for (int i: y) if (i != -1) {
        cur += i;
        if (a) c += i, d += i, cur += i, a --;
        if (b) d += i, cur += i, b --;
    }
    
    int posi = 0;
    if (x != n-1) {
        if (y[0] == 10) posi = 2;
        else if (y[0]+y[1] == 10) posi = 1;
    }
    
    if (x >= 2 && a == 0 && num[x-2] != -1 && c != num[x-2]) return;
    if (x >= 1 && b == 0 && num[x-1] != -1 && d != num[x-1]) return;
    if (posi == 0 && num[x] != -1 && cur != num[x]) return;
    M[b][posi][d][cur] += val;
}

char get(int j) {
    if (j == 10) return 'x';
    return char('0'+j);
}
bool ok(int x, int y) {
    if (x < 0) return 1;
    if (num[x] == -1) return 1;
    return num[x] == y;
}

ll TMP[2][301][11], ans;

void TRI(int a, int b, int c, int d, int x, int i) {
    ll val = m[a][b][c][d];
    if (tmp[x][0] != '?' && tmp[x][0] != get(i)) return;
    
    int cur = d+i;
    if (a) a --, c += i, d += i, cur += i;
    if (b) b --, d += i, cur += i; 
    
    if (a == 0 && !ok(x-2,c)) return;
    if (b == 0 && !ok(x-1,d)) return;
    TMP[b][d][i] += val;
}

void TRI2(int b, int c, int i, int x, int j) {
    if (i+j > 10) return;
    ll val = TMP[b][c][i];
    int cur = c+i;
    if (i+j == 10) {
        if (i == 10) {
            if (tmp[x][1] == '?' || tmp[x][1] == '-') {
                M[b][2][c][cur] += val;
            }
        } else {
            cur += j;
            if (tmp[x][1] == '?' || tmp[x][1] == '/') {
                if (b) b --, c += j, cur += j;
                if (!ok(x-1,c)) return;
                M[b][1][c][cur] += val;
            }
        }
    } else {
        cur += j;
        if (b) b --, c += j, cur += j;
        if (!ok(x-1,c)) return;
        if (!ok(x,cur)) return;
        if (tmp[x][1] == '?' || tmp[x][1] == get(j)) {
            M[0][0][c][cur] += val;
        }
    }
}

ll twoStrike[301], oneStrike[301][10], lastChance[301], noChance[301];

void TRITRI(int b, int c, int i, int x, int j) { // CHECK
    ll val = TMP[b][c][i]; 
    int cur = c+i;
    if (i == 10) {
        if (tmp[x][1] == '?' || tmp[x][1] == get(j)) {
            cur += j;
            if (b) b --, c += j, cur += j;
            if (!ok(x-1,c)) return;
            if (j == 10) twoStrike[cur] += val;
            else oneStrike[cur][j] += val;
        }
        return;
    } 
    if (i+j > 10) return; 
    if (i+j == 10) {
        cur += j;
        if (tmp[x][1] == '?' || tmp[x][1] == '/') {
            if (b) b --, c += j, cur += j;
            if (!ok(x-1,c)) return;
            lastChance[cur] += val;
        }
    } else {
        cur += j;
        if (tmp[x][1] == '?' || tmp[x][1] == get(j)) {
            if (b) b --, c += j, cur += j;
            if (!ok(x-1,c)) return;
            noChance[cur] += val;
        }
    }
}

void finish() {
    F0R(x,301) F0R(i,11) if (tmp[n-1][2] == '?' || tmp[n-1][2] == get(i)) {
        int z = x+i;
        if (num[n-1] == -1 || num[n-1] == z) ans += twoStrike[x];
    }
    F0R(x,301) F0R(i,10) F0R(j,11-i) {
        if (i+j == 10) {
            if (tmp[n-1][2] == '?' || tmp[n-1][2] == '/') {
                int z = x+j;
                if (num[n-1] == -1 || num[n-1] == z) ans += oneStrike[x][i];
            }
        } else {
            if (tmp[n-1][2] == '?' || tmp[n-1][2] == get(j)) {
                int z = x+j;
                if (num[n-1] == -1 || num[n-1] == z) ans += oneStrike[x][i];
            }
        }
    }
    
    F0R(x,301) F0R(j,11) 
        if (tmp[n-1][2] == '?' || tmp[n-1][2] == get(j)) {
            int z = x+j;
            if (num[n-1] == -1 || num[n-1] == z) ans += lastChance[x];
        }
    
    F0R(x,301) 
        if (tmp[n-1][2] == '?' || tmp[n-1][2] == '-') 
            if (num[n-1] == -1 || num[n-1] == x) 
                ans += noChance[x];
}

void process(int x) {
    vector<vi> posi;
    
    if (x != n-1) {
        memset(TMP,0,sizeof TMP);
        F0R(a,2) F0R(b,3) F0R(c,301) FOR(d,c,301) if (m[a][b][c][d])
            F0R(i,11) TRI(a,b,c,d,x,i);
        F0R(b,2) F0R(c,301) F0R(i,11) if (TMP[b][c][i])
            F0R(j,11) TRI2(b,c,i,x,j);
    } else {
        memset(TMP,0,sizeof TMP);
        F0R(a,2) F0R(b,3) F0R(c,301) FOR(d,c,301) if (m[a][b][c][d])
            F0R(i,11) TRI(a,b,c,d,x,i);
        F0R(b,2) F0R(c,301) F0R(i,11) if (TMP[b][c][i])
            F0R(j,11) TRITRI(b,c,i,x,j);
        finish();
    }
            
    F0R(a,2) F0R(b,3) F0R(c,301) FOR(d,c,301) {
        m[a][b][c][d] = M[a][b][c][d];
        M[a][b][c][d] = 0;
    }
}

void solve() {
    cin >> n;
    string s; cin >> s;
    F0R(i,n-1) tmp[i] = s.substr(2*i,2);
    tmp[n-1] = s.substr(2*(n-1),3);
    F0R(i,n) cin >> num[i];
    
    memset(m,0,sizeof m);
    memset(twoStrike,0,sizeof twoStrike);
    memset(oneStrike,0,sizeof oneStrike);
    memset(lastChance,0,sizeof lastChance);
    memset(noChance,0,sizeof noChance);
    
    m[0][0][0][0] = 1;
    ans = 0;
    F0R(i,n) process(i);
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> q;
    F0R(i,q) solve();
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18