Advertisement
Guest User

Untitled

a guest
Apr 5th, 2017
302
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<cmath>
  7. #include<string>
  8. #include<sstream>
  9. #include<set>
  10. #include<map>
  11. #include<stack>
  12. #include<queue>
  13. #include<deque>
  14. #include<memory.h>
  15. #include<ctime>
  16. #include<cassert>
  17. #include<limits.h>
  18. #include<unordered_map>
  19. #include<unordered_set>
  20.  
  21. #define pb push_back
  22. #define sz(a) (int)a.size()
  23. //#define bs binary_search
  24. #define np next_permutation
  25. #define mp make_pair
  26. #define all(a) a.begin(),a.end()
  27. #define forn(i, n) for (int i = 0; i < n; ++i)
  28. #define forv(i, v) for (int i = 0; i < sz(v); ++i)
  29. #define forab(i, a, b) for (int i = a; i <= b; i++)
  30. #define forabd(i, a, b) for (int i = a; i >= b; i--)
  31. #define _(a, b) memset(a, b, sizeof a)
  32. #define pii pair<int, int>
  33. #define pll pair<long long, long long>
  34.  
  35. typedef long long ll;
  36. typedef unsigned long long ull;
  37.  
  38. using namespace std;
  39.  
  40. template<class T> inline T sqr(T x) { return x * x; }
  41.  
  42. const double pi = acos(-1.0), eps = 1e-9, e = exp(1.0);
  43. const int INF = 1000 * 1000 * 1000 + 7, MAXN = 100005, MOD = 1000000007, MAXBIT = 30, pHash = 53;
  44. const ll INFL = 1e+18;
  45.  
  46. void prepare(string s) {
  47. #ifdef _DEBUG
  48.     freopen("input.txt", "r", stdin);
  49.     //freopen("output.txt","w",stdout);
  50. #else
  51.     if (sz(s) != 0) {
  52.         freopen((s + ".in").c_str(), "r", stdin);
  53.         freopen((s + ".out").c_str(), "w", stdout);
  54.     }
  55. #endif
  56. }
  57.  
  58. int p, k, ans, g[1005];
  59. vector<int> a[105];
  60.  
  61. void read() {
  62.     cin >> p >> k;
  63.     forn(i, p) {
  64.         int n;
  65.         cin >> n;
  66.         a[i].resize(n);
  67.         forn(j, n) cin >> a[i][j];
  68.     }
  69. }
  70.  
  71. int mex(vector<int> &a) {
  72.     set<int> s(all(a));
  73.     for (int i = 0; ; i++) {
  74.         if (!s.count(i)) {
  75.             return i;
  76.         }
  77.     }
  78. }
  79.  
  80. int grandy(int n, int pile) {
  81.     if (n < 0) {
  82.         return 1;
  83.     }
  84.     if (g[n] != -1) {
  85.         return g[n];
  86.     }
  87.     vector<int> v, pp;
  88.  
  89.     for (int i = 0; i <= k; i++) {
  90.         if (n - i <= 0) break;
  91.         pp.push_back(i + a[pile][n-i-1]);
  92.     }
  93.  
  94.     forv(i, pp) {
  95.         v.push_back(grandy(n-pp[i], pile));
  96.     }
  97.     g[n] = mex(v);
  98.     return g[n];
  99. }
  100.  
  101. void solve() {
  102.     forn(i, p) {
  103.         _(g, -1);
  104.  
  105.         g[0] = 0;
  106.         reverse(all(a[i]));
  107.         int res = grandy(sz(a[i]), i);
  108.         ans ^= res;
  109.     }
  110.  
  111.     ans != 0 ? cout << "Alice can win." : cout << "Bob will win.";
  112. }
  113.  
  114. int main() {
  115.     prepare("");
  116.  
  117.     read();
  118.     solve();
  119.  
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement