Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5. typedef pair<LL, LL> PII;
  6. typedef vector<LL> VI;
  7. #define MP make_pair
  8. #define PB push_back
  9. #define X first
  10. #define Y second
  11.  
  12. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  13. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  14. #define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  15. #define ALL(a) a.begin(), a.end()
  16. #define SZ(a) (int)((a).size())
  17. #define FILL(a, value) memset(a, value, sizeof(a))
  18. #define debug(a) cout << #a << " = " << a << endl;
  19.  
  20. const double PI = acos(-1.0);
  21. const LL INF = 1000 * 1000 * 1000 + 47;
  22. const LL LINF = INF * INF;
  23.  
  24. const int N = 10007;
  25. int a[N];
  26. int res[N];
  27. int u[10005];
  28. int cnt[8];
  29. int cnt2[8];
  30. int idx = 0;
  31. int q[8];
  32. int prefDob[8];
  33. int curHsh;
  34. int n;
  35. void go()
  36. {
  37.     if(idx == n)
  38.     {
  39.         int xr = 0;
  40.         for(int mask = 0; mask < (1 << n); mask++)
  41.         {
  42.             int hsh = 0;
  43.             for(int i = 0; i < n; i++)
  44.             {
  45.                 if(mask & (1 << i))
  46.                     hsh += cnt2[i] * prefDob[i];
  47.                 else
  48.                     hsh += (cnt[i] - cnt2[i] - 1) * prefDob[i];
  49.             }
  50.  
  51.             xr ^= res[hsh];
  52.  
  53.  
  54.         }
  55.         u[xr] = 1;
  56.         return ;
  57.     }
  58.     for(int i = 0; i <= cnt[idx] / 2; i++)
  59.     {
  60.         cnt2[idx] = i;
  61.  
  62.         curHsh += prefDob[idx];
  63.         if(__gcd(i , cnt[idx]) > 1 && __gcd(cnt[idx] - i - 1 , cnt[idx]) > 1)
  64.             continue;
  65.         idx++;
  66.         go();
  67.         idx--;
  68.     }
  69.     cnt2[idx] = 0;
  70.     for(int i = 0; i <= cnt[idx] / 2; i++)
  71.         curHsh -= prefDob[idx];
  72.  
  73. }
  74. int main()
  75. {
  76.   ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  77.     //freopen("In.txt", "r", stdin);
  78.   //freopen("Out.txt", "w", stdout);
  79.     cin >> n;
  80.     bool was1 = false;
  81.     int dob = 1;
  82.     for(int i = 0; i < n; i++)
  83.     {
  84.         cin >> a[i];
  85.         prefDob[i] = dob;
  86.         dob *= (a[i] + 1);
  87.         was1 |= a[i] == 1;
  88.     }
  89.     if(was1)
  90.     {
  91.         cout << "Archie" << endl;
  92.         return 0;
  93.     }
  94.     if(n == 1)
  95.     {
  96.         cout << ((a[0] % 2) ? "Archie" : "Barik");
  97.         return 0;
  98.     }
  99.     for(int hsh = 0; hsh < dob; hsh++)
  100.     {
  101.         int hsh2 = hsh;
  102.         bool was1 = false , was0 = false;
  103.         for(int i = 0; i < n; i++)
  104.         {
  105.             cnt[i] = hsh2 % (a[i] + 1);
  106.             hsh2 /= a[i] + 1;
  107.             was1 |= cnt[i] == 1;
  108.             was0 |= cnt[i] == 0;
  109.  
  110.         }
  111.         if(was0)
  112.             continue;
  113.         if(was1)
  114.         {
  115.             res[hsh] = 1;
  116.             continue;
  117.         }
  118.  
  119.         memset(u , 0 , sizeof u);
  120.         go();
  121.  
  122.         int kek = 0;
  123.         while(u[kek])
  124.             kek++;
  125.         res[hsh] = kek;
  126.  
  127.     }
  128.     cout << (res[dob - 1] ? "Archie" : "Barik");
  129.     return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement