답안 #60213 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60213	2018-07-23T20:52:38 Z	Benq	Bowling (BOI15_bow)	C++11	42 / 100	1000 ms	1016 KB

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

void process(int x) {
    if (x != n-1) {
        F0R(X,2) F0R(Y,3) for (auto a: m[X][Y]) {
            tri(X,Y,a,x,{10,-1});
            F0R(i,10) F0R(j,11-i) tri(X,Y,a,x,{i,j});
        }
    } else {
        F0R(X,2) F0R(Y,3) for (auto a: m[X][Y]) {
            F0R(i,11) tri(X,Y,a,x,{10,10,i});
            F0R(i,10) F0R(j,11-i) tri(X,Y,a,x,{10,i,j});
            F0R(i,10) F0R(j,11) tri(X,Y,a,x,{i,10-i,j});
            F0R(i,10) F0R(j,10-i) tri(X,Y,a,x,{i,j,-1});
        }
    }
    F0R(i,2) F0R(j,3) {
        swap(m[i][j],M[i][j]);
        M[i][j].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];
    
    F0R(i,2) F0R(j,3) m[i][j].clear();
    m[0][0][{0,0}] = 1;
    F0R(i,n) process(i);
    ll ans = 0;
    for (auto a: m[0][0]) 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
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	376 KB	Output is correct
2	Correct	15 ms	488 KB	Output is correct
3	Correct	8 ms	488 KB	Output is correct
4	Correct	7 ms	488 KB	Output is correct
5	Correct	6 ms	488 KB	Output is correct
6	Correct	9 ms	600 KB	Output is correct
7	Correct	84 ms	632 KB	Output is correct
8	Correct	72 ms	632 KB	Output is correct
9	Correct	48 ms	632 KB	Output is correct
10	Correct	75 ms	692 KB	Output is correct
11	Correct	49 ms	692 KB	Output is correct
12	Correct	15 ms	692 KB	Output is correct
13	Correct	5 ms	692 KB	Output is correct
14	Correct	25 ms	692 KB	Output is correct
15	Correct	7 ms	692 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	352 ms	692 KB	Output is correct
2	Correct	114 ms	696 KB	Output is correct
3	Correct	153 ms	756 KB	Output is correct
4	Correct	43 ms	756 KB	Output is correct
5	Correct	75 ms	756 KB	Output is correct
6	Correct	67 ms	756 KB	Output is correct
7	Correct	133 ms	876 KB	Output is correct
8	Correct	207 ms	876 KB	Output is correct
9	Correct	82 ms	876 KB	Output is correct
10	Correct	403 ms	876 KB	Output is correct
11	Correct	552 ms	1016 KB	Output is correct
12	Correct	309 ms	1016 KB	Output is correct
13	Correct	619 ms	1016 KB	Output is correct
14	Correct	76 ms	1016 KB	Output is correct
15	Correct	62 ms	1016 KB	Output is correct
16	Correct	64 ms	1016 KB	Output is correct
17	Correct	90 ms	1016 KB	Output is correct
18	Execution timed out	1074 ms	1016 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	439 ms	1016 KB	Output is correct
2	Correct	17 ms	1016 KB	Output is correct
3	Correct	12 ms	1016 KB	Output is correct
4	Correct	13 ms	1016 KB	Output is correct
5	Correct	29 ms	1016 KB	Output is correct
6	Correct	18 ms	1016 KB	Output is correct
7	Correct	21 ms	1016 KB	Output is correct
8	Correct	19 ms	1016 KB	Output is correct
9	Correct	13 ms	1016 KB	Output is correct
10	Correct	32 ms	1016 KB	Output is correct
11	Correct	20 ms	1016 KB	Output is correct
12	Correct	22 ms	1016 KB	Output is correct
13	Correct	24 ms	1016 KB	Output is correct
14	Correct	38 ms	1016 KB	Output is correct
15	Correct	53 ms	1016 KB	Output is correct
16	Correct	39 ms	1016 KB	Output is correct
17	Correct	44 ms	1016 KB	Output is correct
18	Correct	12 ms	1016 KB	Output is correct
19	Correct	17 ms	1016 KB	Output is correct
20	Correct	20 ms	1016 KB	Output is correct
21	Correct	16 ms	1016 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	639 ms	1016 KB	Output is correct
2	Correct	162 ms	1016 KB	Output is correct
3	Correct	356 ms	1016 KB	Output is correct
4	Correct	233 ms	1016 KB	Output is correct
5	Correct	147 ms	1016 KB	Output is correct
6	Correct	99 ms	1016 KB	Output is correct
7	Correct	132 ms	1016 KB	Output is correct
8	Correct	110 ms	1016 KB	Output is correct
9	Correct	123 ms	1016 KB	Output is correct
10	Execution timed out	1072 ms	1016 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	376 KB	Output is correct
2	Correct	15 ms	488 KB	Output is correct
3	Correct	8 ms	488 KB	Output is correct
4	Correct	7 ms	488 KB	Output is correct
5	Correct	6 ms	488 KB	Output is correct
6	Correct	9 ms	600 KB	Output is correct
7	Correct	84 ms	632 KB	Output is correct
8	Correct	72 ms	632 KB	Output is correct
9	Correct	48 ms	632 KB	Output is correct
10	Correct	75 ms	692 KB	Output is correct
11	Correct	49 ms	692 KB	Output is correct
12	Correct	15 ms	692 KB	Output is correct
13	Correct	5 ms	692 KB	Output is correct
14	Correct	25 ms	692 KB	Output is correct
15	Correct	7 ms	692 KB	Output is correct
16	Correct	352 ms	692 KB	Output is correct
17	Correct	114 ms	696 KB	Output is correct
18	Correct	153 ms	756 KB	Output is correct
19	Correct	43 ms	756 KB	Output is correct
20	Correct	75 ms	756 KB	Output is correct
21	Correct	67 ms	756 KB	Output is correct
22	Correct	133 ms	876 KB	Output is correct
23	Correct	207 ms	876 KB	Output is correct
24	Correct	82 ms	876 KB	Output is correct
25	Correct	403 ms	876 KB	Output is correct
26	Correct	552 ms	1016 KB	Output is correct
27	Correct	309 ms	1016 KB	Output is correct
28	Correct	619 ms	1016 KB	Output is correct
29	Correct	76 ms	1016 KB	Output is correct
30	Correct	62 ms	1016 KB	Output is correct
31	Correct	64 ms	1016 KB	Output is correct
32	Correct	90 ms	1016 KB	Output is correct
33	Execution timed out	1074 ms	1016 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #60213

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 0 / 17.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 23.0

Subtask #5 0 / 18.0

Subtask #1
16.0 / 16.0

Subtask #2
0 / 17.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 23.0

Subtask #5
0 / 18.0