| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 60200 |
2018-07-23T20:36:06 Z |
Benq |
Bowling (BOI15_bow) |
C++11 |
|
494 ms |
1004 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;
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
367 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
494 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
