Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<vector>
- #include<cmath>
- #include<string>
- #include<sstream>
- #include<set>
- #include<map>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<memory.h>
- #include<ctime>
- #include<cassert>
- #include<limits.h>
- #include<unordered_map>
- #include<unordered_set>
- #define pb push_back
- #define sz(a) (int)a.size()
- //#define bs binary_search
- #define np next_permutation
- #define mp make_pair
- #define all(a) a.begin(),a.end()
- #define forn(i, n) for (int i = 0; i < n; ++i)
- #define forv(i, v) for (int i = 0; i < sz(v); ++i)
- #define forab(i, a, b) for (int i = a; i <= b; i++)
- #define forabd(i, a, b) for (int i = a; i >= b; i--)
- #define _(a, b) memset(a, b, sizeof a)
- #define pii pair<int, int>
- #define pll pair<long long, long long>
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
- template<class T> inline T sqr(T x) { return x * x; }
- const double pi = acos(-1.0), eps = 1e-9, e = exp(1.0);
- const int INF = 1000 * 1000 * 1000 + 7, MAXN = 100005, MOD = 1000000007, MAXBIT = 30, pHash = 53;
- const ll INFL = 1e+18;
- void prepare(string s) {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- //freopen("output.txt","w",stdout);
- #else
- if (sz(s) != 0) {
- freopen((s + ".in").c_str(), "r", stdin);
- freopen((s + ".out").c_str(), "w", stdout);
- }
- #endif
- }
- int p, k, ans, g[1005];
- vector<int> a[105];
- void read() {
- cin >> p >> k;
- forn(i, p) {
- int n;
- cin >> n;
- a[i].resize(n);
- forn(j, n) cin >> a[i][j];
- }
- }
- int mex(vector<int> &a) {
- set<int> s(all(a));
- for (int i = 0; ; i++) {
- if (!s.count(i)) {
- return i;
- }
- }
- }
- int grandy(int n, int pile) {
- if (n < 0) {
- return 1;
- }
- if (g[n] != -1) {
- return g[n];
- }
- vector<int> v, pp;
- for (int i = 0; i <= k; i++) {
- if (n - i <= 0) break;
- pp.push_back(i + a[pile][n-i-1]);
- }
- forv(i, pp) {
- v.push_back(grandy(n-pp[i], pile));
- }
- g[n] = mex(v);
- return g[n];
- }
- void solve() {
- forn(i, p) {
- _(g, -1);
- g[0] = 0;
- reverse(all(a[i]));
- int res = grandy(sz(a[i]), i);
- ans ^= res;
- }
- ans != 0 ? cout << "Alice can win." : cout << "Bob will win.";
- }
- int main() {
- prepare("");
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement