fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int T;
  9.     if (!(cin >> T)) return 0;
  10.     while (T--) {
  11.         int N;
  12.         cin >> N;
  13.         vector<int> A(N);
  14.         for (int i = 0; i < N; ++i) cin >> A[i];
  15.  
  16.         // cnt[b] : number of elements whose MSB is b (0-based)
  17.         const int MAXB = 31; // Ai <= 1e9 < 2^30, but keep 31 for safety
  18.         vector<int> cnt(MAXB+1, 0);
  19.         for (int x : A) {
  20.             int b = 0;
  21.             // find msb position (0-based)
  22.             for (int i = MAXB; i >= 0; --i) {
  23.                 if (x & (1 << i)) {
  24.                     b = i;
  25.                     break;
  26.                 }
  27.             }
  28.             cnt[b]++;
  29.         }
  30.  
  31.         // find highest bit B with cnt[B] > 0
  32.         int B = -1;
  33.         for (int i = MAXB; i >= 0; --i) {
  34.             if (cnt[i] > 0) {
  35.                 B = i;
  36.                 break;
  37.             }
  38.         }
  39.         // safety
  40.         if (B == -1) {
  41.             // all zero? but constraints Ai >= 1 so shouldn't happen
  42.             cout << "Bob\n";
  43.             continue;
  44.         }
  45.  
  46.         int k = cnt[B];
  47.         if (k % 2 == 0) {
  48.             cout << "Bob\n";
  49.         } else {
  50.             // k is odd
  51.             if (k % 4 == 1) {
  52.                 cout << "Alice\n";
  53.             } else { // k % 4 == 3
  54.                 int rest = N - k;
  55.                 if (rest % 2 == 1) cout << "Alice\n";
  56.                 else cout << "Bob\n";
  57.             }
  58.         }
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
4
3
3 4 6
3
7 7 7
3
9 3 5
10
1 9 1 3 7 9 10 9 7 3
stdout 
Bob
Bob
Alice
Bob
https://ideone.com/5DXyDI
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 hours 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!