Submission #60200

#	Time	Username	Problem	Language	Result	Execution time	Memory
60200		Benq	Bowling (BOI15_bow)	C++11	0 / 100	494 ms	1004 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;


int q, n, num[10];
map<pair<pi,pi>,ll> m, M;
string tmp[10];

bool match(string bad, vi nex) {
    int lst = 0;
    F0R(i,sz(bad)) {
        if (bad[i] == '?') lst = nex[i];
        else {
            int val;
            if (bad[i] == '-') val = -1;
            else if (bad[i] == 'x') val = 10;
            else if (bad[i] == '/') val = 10-lst;
            else val = bad[i]-'0';
            if (val != nex[i]) return 0;
            lst = val;
        }
    }
    return 1;
}


void tri(pair<pair<pi,pi>, ll> A, int x, vi y) {
    if (!match(tmp[x],y)) return;
    pair<pi,pi> a = A.f;
    
    int cur = a.s.s;
    for (int i: y) if (i != -1) {
        cur += i;
        if (a.f.f) {
            a.s.f += i, a.s.s += i, cur += i;
            a.f.f --;
        }
        if (a.f.s) {
            a.s.s += i, cur += i;
            a.f.s --;
        }
    }
    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.f.f == 0 && num[x-2] != -1 && a.s.f != num[x-2]) return;
    if (x >= 1 && a.f.s == 0 && num[x-1] != -1 && a.s.s != num[x-1]) return;
    if (posi == 0 && num[x] != -1 && cur != num[x]) return;
    M[{{a.f.s,posi},{a.s.s,cur}}] += A.s;
}

void process(int x) {
    if (x != n-1) {
        for (auto a: m) {
            tri(a,x,{10,-1});
            F0R(i,10) F0R(j,11-i) tri(a,x,{i,j});
        }
    } else {
        for (auto a: m) {
            F0R(i,11) tri(a,x,{10,10,i});
            F0R(i,10) F0R(j,11-i) tri(a,x,{10,i,j});
            F0R(i,10) F0R(j,11) tri(a,x,{i,10-i,j});
            F0R(i,10) F0R(j,10-i) tri(a,x,{i,j,-1});
        }
    }
    m = M; M.clear();
}

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];
    
    m.clear();
    m[{{0,0},{0,0}}] = 1;
    F0R(i,n) {
        process(i);
        /*cout << i << " " << sz(m) << "\n";
        for (auto a: m) cout << a.f.f.f << " " << a.f.f.s << " " << a.f.s.f << " " << a.f.s.s << "\n";
        cout << "\n";*/
    }
    ll ans = 0;
    for (auto a: m) ans += a.s;
    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: 0 / 16
• Subtask 2: 0 / 17
• Subtask 3: 0 / 26
• Subtask 4: 0 / 23
• Subtask 5: 0 / 18