fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <deque>
  7.  
  8. using namespace std;
  9.  
  10. int f(int x, int y) {
  11.   return !x || !y;
  12. }
  13.  
  14. int main() {
  15.   int T;
  16.   cin >> T;
  17.   while (T--) {
  18.     int q;
  19.     string s, t;
  20.     cin >> t >> s >> q;
  21.     s = '0' + s;
  22.     t = '0' + t;
  23.     for (char &c : s) c -= '0';
  24.     for (char &c : t) c -= '0';
  25.     const int n = max(s.size(), t.size());
  26.     s.resize(n * 2 + 2);
  27.     t.resize(n * 2 + 2);
  28.     vector<int> ys(q), xs(q);
  29.     vector<vector<int>> check(n * 2 + 1);
  30.     for (int i = 0; i < q; i++) {
  31.       scanf("%d %d", &ys[i], &xs[i]);
  32.       if ((ys[i] + xs[i]) % 2 == 0) {
  33.         check[ys[i] + xs[i]].push_back(i);
  34.       } else {
  35.         check[ys[i] + xs[i] - 1].push_back(i);
  36.       }
  37.     }
  38.     vector<int> ans(q);
  39.     deque<int> a;
  40.     int i = 0;
  41.     while (i <= n * 2) {
  42.       for (int j : check[i]) {
  43.         if ((ys[j] + xs[j]) % 2 == 0) {
  44.           ans[j] = a[xs[j]];
  45.         } else {
  46.           ans[j] = f(a[xs[j]], a[xs[j] - 1]);
  47.         }
  48.       }
  49.       if (i <= 7) {
  50.         deque<int> b;
  51.         for (int i = 0; i + 1 < a.size(); i++) {
  52.           b.push_back(f(a[i], a[i + 1]));
  53.         }
  54.         b.push_front(s[i + 1]);
  55.         b.push_back(t[i + 1]);
  56.         a = b;
  57.         i++;
  58.       } else {
  59.         const int m = a.size();
  60.         int l0 = f(s[i + 1], f(a[0], a[1]));
  61.         int l1 = f(f(a[0], a[1]), f(a[1], a[2]));
  62.         int r0 = f(f(a[m - 3], a[m - 2]), f(a[m - 2], a[m - 1]));
  63.         int r1 = f(f(a[m - 2], a[m - 1]), t[i + 1]);
  64.         a[0] = l0;
  65.         a[1] = l1;
  66.         a[m - 2] = r0;
  67.         a[m - 1] = r1;
  68.         a.push_front(s[i + 2]);
  69.         a.push_back(t[i + 2]);
  70.         i += 2;
  71.       }
  72.     }
  73.     for (int i = 0; i < q; i++) {
  74.       printf("%d", ans[i]);
  75.     }
  76.     putchar('\n');
  77.   }
  78. }
  79.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uXVcpK
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!