fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define yo_con_marcelita
  3. #define F first
  4. #define S second
  5. #define pb push_back
  6. #define eb emplace_back
  7. #define ln cout<<endl;
  8. #define sz(x) int((x).size())
  9. #define all(x) (x).begin(), (x).end()
  10. #define rall(x) (x).rbegin(), (x).rend()
  11. #define read(x) for(auto &el : x) cin >> el;
  12. #define For(i,s,n) for(int i=s; i < int(n); ++i)
  13. #define dFor(i,f,n) for (int i = n - 1; i >= f; --i)
  14. #define DBG(x) cout << #x << " = " << x << endl;
  15. #define print(x) for(auto &el : x) {cout << el << " ";} cout<<endl;
  16. #define lw(c, x) int(lower_bound((c).begin(), (c).end(), (x)) - (c).begin())
  17. #define up(c, x) int(upper_bound((c).begin(), (c).end(), (x)) - (c).begin())
  18. #define sino(b) cout<<(b ? "YES\n":"NO\n");
  19. #define syso(x) cout<< (x) <<endl;
  20. #define kill(x) {cout<< (x) <<endl; return;}
  21. using namespace std;
  22. typedef long long ll;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int,int> pii;
  27. typedef pair<ll,ll> pll;
  28. ll gcd(ll a, ll b){while(b){a%=b; swap(a,b);} return a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);}
  29. int lg2(const int &x) { return 31-__builtin_clz(x);} // int lg2(const ll &x) {return 63-__builtin_clzll(x);}
  30. // Para leer e imprimir .txt
  31. // freopen("input.txt", "r", stdin);
  32. // freopen("output.txt", "w", stdout);
  33.  
  34. struct iterativetree {
  35.     int n;
  36.     ll neutro = 0ll; //valor neutro, no afecta las operaciones
  37.     vector<ll> t;
  38.  
  39.     iterativetree(vector<int> &v) {
  40.         n = v.size();
  41.         t.assign(2*n, neutro);
  42.         for (int i = 0; i < n; i++) t[i+n] = v[i];
  43.         // for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
  44.     }
  45.  
  46.     // RANGE UPDATES & SINGLE QUERY
  47.     ll query(int p) { // retorna el valor en la posicion p
  48.         ll res = 0;
  49.         for (p += n; p > 0; p >>= 1) res += t[p];
  50.         return res;
  51.     }
  52.  
  53.     void upd(int l, int r, ll value) {  // [l, r]
  54.         for (l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
  55.             if (l&1) t[l++] += value;
  56.             if (r&1) t[--r] += value;
  57.         }
  58.     }
  59. };
  60.  
  61.  
  62. void solve() {
  63.     int n, k; cin >> n >> k;
  64.     vi a(n); read(a)
  65.     iterativetree t(a);
  66.     ll ans = 0;
  67.     for (int i=n-1;i>=0;i--) {
  68.         ll v = t.query(i);
  69.         if (!v) continue;
  70.         ans += v;
  71.         if (i) t.upd(max(0,i-k),i-1,v);
  72.     }
  73.     // syso(ans)
  74.     cout << (ans&1ll ? "Alice" : "Bob") << endl;
  75. }
  76.  
  77. int main(){
  78.     yo_con_marcelita
  79.     int t = 1;
  80.     cin >> t;
  81.     while (t--) {
  82.         solve();
  83.     }
  84.     return 0;
  85. }
  86. //VisualSaquenASebastianDelEquipoPorFavorCode
Success #stdin #stdout 0.01s 5352KB
comments (?)
stdin
copy 
5
2 1
1 1
3 2
0 0 1
4 1
0 0 1 0
5 2
1 2 3 4 5
3 1
2 5 2
stdout
copy 
Alice
Bob
Alice
Alice
Bob
https://ideone.com/5QTu9j
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!