daily pastebin goal
42%
SHARE
TWEET

Untitled

a guest May 16th, 2018 133 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8. #include <cassert>
  9. #define PB push_back
  10. #define MP make_pair
  11. #define sz(v) (ll((v).size()))
  12. #define forn(i,n) for(ll i = 0; i < (n); ++i)
  13. #define forv(i,v) forn(i,sz(v))
  14. #define rep(i,l,r) for (ll i = (l); i < (r); ++i)
  15. #define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
  16. #define all(v) (v).begin(), (v).end()
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef pair<ll, ll> pii;
  22. typedef vector<ll> vi;
  23. typedef vector<vi> vvi;
  24.  
  25.  
  26. const int N = 20;
  27.  
  28.  
  29. void main2() {
  30.     int n; cin >> n;
  31.     vi a( (1 << n) + 1 );
  32.     vvi sum(n + 1, vi(1 + (1 << n)));
  33.     vvi dp(n + 1, vi(1 + (1 << n)));
  34.     rep(i, 1, (1 << n) + 1) {
  35.         char ch; cin >> ch; a[i] = ch;
  36.         if (n % 2 == 0) {
  37.             if (a[i] == 'B') dp[0][i] = 1;
  38.         } else if (a[i] == 'A') dp[0][i] = 1;
  39.         sum[0][i] = sum[0][i - 1] + dp[0][i];
  40.     }
  41.  
  42.     for (int i = 1; i <= n; i++) {
  43.         for (int j = 1; j <= (1 << n) - (1 << i) + 1; j++) {
  44.             ll rb = j + (1 << (i - 1)), lb = j - 1;
  45.             ll canwin = (sum[i - 1][rb] - sum[i - 1][lb]) == 0;
  46.             dp[i][j] = canwin;
  47.             sum[i][j] = dp[i][j] + sum[i][j - 1];
  48.         }
  49.     }
  50.     cout << (dp[n][1] == 0 ? "A" : "B" ) << endl;
  51. }
  52.  
  53.  
  54. int main() {
  55.     ios::sync_with_stdio(0); cin.tie(0);
  56.     int t; cin >> t;
  57.     forn(i, t) {
  58.         main2();
  59.     }
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top