fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. long long gcd(long long x, long long y) {
  9.   while (y != 0) {
  10.     long long tmp = x;
  11.     x = y;
  12.     y = tmp % x;
  13.   }
  14.   return x;
  15. }
  16.  
  17. long long lcm(long long x, long long y) {
  18.   return x / gcd(x, y) * y;
  19. }
  20.  
  21. struct Matrix {
  22.   vector<int> a;
  23.   int h, w;
  24.  
  25.   Matrix(int h_, int w_) : a(h_ * w_), h(h_), w(w_) {};
  26.  
  27.   int &operator()(int i, int j) {
  28.     return a[i * w + j];
  29.   }
  30. };
  31.  
  32. int main() {
  33.   int T;
  34.   scanf("%d", &T);
  35.   while (T--) {
  36.     long long h1, w1, h2, w2;
  37.     string s, t;
  38.     cin >> h1 >> w1 >> s >> h2 >> w2 >> t;
  39.     long long h = lcm(h1, h2);
  40.     long long w = lcm(w1, w2);
  41.     Matrix sum(h2 + 1, w2 + 1);
  42.     for (int i = 0; i < h2; i++) 
  43.       for (int j = 0; j < w2; j++) 
  44.         sum(i + 1, j + 1) = sum(i + 1, j) + sum(i, j + 1) - sum(i, j) + (t[i * w2 + j] == '1');
  45.     long long sy = h / h2;
  46.     long long sx = w / w2;
  47.     long long ans = 0;
  48.     auto calc = [&](long long y, long long x) {
  49.       long long yy = y / sy * sy;
  50.       long long xx = x / sx * sx;
  51.       long long Y = yy / sy;
  52.       long long X = xx / sx;
  53.       long long res = 0;
  54.       if (y > yy && x > xx)
  55.         res += (t[Y * w2 + X] == '1') * (y - yy) * (x - xx);
  56.       if (x > xx) {
  57.         res += (sum(Y, X + 1) - sum(Y, X)) * (x - xx) * sy;
  58.       }
  59.       if (y > yy)
  60.         res += (sum(Y + 1, X) - sum(Y, X)) * (y - yy) * sx;
  61.       res += sum(Y, X) * sy * sx;
  62.       return res;
  63.     };
  64.     for (long long i = 0; i < h1; i++) {
  65.       for (long long j = 0; j < w1; j++) {
  66.         long long i0 = i * (h / h1);
  67.         long long j0 = j * (w / w1);
  68.         long long i1 = (i + 1) * (h / h1);
  69.         long long j1 = (j + 1) * (w / w1);
  70.         long long v = calc(i0, j0) - calc(i1, j0) - calc(i0, j1) + calc(i1, j1);
  71.         if (s[i * w1 + j] == '0') 
  72.           v = (i1 - i0) * (j1 - j0) - v;
  73.         ans += v;
  74.       }
  75.     }
  76.     cout << ans << endl;
  77.   }
  78. }
  79.  
Runtime error #stdin #stdout #stderr 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/bO9TAR
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!