Submission #60215

#TimeUsernameProblemLanguageResultExecution timeMemory
60215BenqBowling (BOI15_bow)C++11
82 / 100
1089 ms1356 KiB
#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) { vector<vi> posi; if (x != n-1) { if (match(tmp[x],{10,-1})) posi.pb({10,-1}); F0R(i,10) F0R(j,11-i) if (match(tmp[x],{i,j})) posi.pb({i,j}); } else { F0R(i,11) if (match(tmp[x],{10,10,i})) posi.pb({10,10,i}); F0R(i,10) F0R(j,11-i) if (match(tmp[x],{10,i,j})) posi.pb({10,i,j}); F0R(i,10) F0R(j,11) if (match(tmp[x],{i,10-i,j})) posi.pb({i,10-i,j}); F0R(i,10) F0R(j,10-i) if (match(tmp[x],{i,j,-1})) posi.pb({i,j,-1}); } for (auto v: posi) F0R(X,2) F0R(Y,3) for (auto a: m[X][Y]) tri(X,Y,a,x,v); 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...