Submission #1296402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296402		kunzaZa183	Sateliti (COCI20_satellti)	C++20	10 / 110	4 ms	4304 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> powvi;
vector<vector<int>> hsh;
signed main() {
  int n, m;
  cin >> n >> m;
  vector<string> vvi(n);
  for (auto &a : vvi) {
    cin >> a;
  }

  for (int i = 0; i < n; i++) {
    vvi[i] += vvi[i];
  }

  for (int i = 0; i < n; i++) {
    vvi.push_back(vvi[i]);
  }

  const int base = 2, mod = 1e9 + 7;

  powvi.resize(n * m + 1);
  powvi[0] = 1;
  for (int i = 1; i <= n * m; i++)
    powvi[i] = 2 * powvi[i - 1] % mod;

  hsh = vector<vector<int>>(vvi.size(), vector<int>(vvi[0].size()));

  for (int i = 0; i < hsh.size(); i++) {
    for (int j = 0; j < hsh[0].size(); j++) {
      hsh[i][j] = (vvi[i][j] == '.') * powvi[i * m + j];
    }
  }

  for (int i = 1; i < hsh.size(); i++) {
    hsh[i][0] += hsh[i - 1][0];
    hsh[i][0] %= mod;
  }

  for (int j = 1; j < hsh[0].size(); j++) {
    hsh[0][j] += hsh[0][j - 1];
    hsh[0][j] %= mod;
  }

  for (int i = 1; i < hsh.size(); i++) {
    for (int j = 1; j < hsh[0].size(); j++) {
      hsh[i][j] += hsh[i - 1][j] + hsh[i][j - 1] - hsh[i - 1][j - 1];
      hsh[i][j] %= mod;
      hsh[i][j] += mod;
      hsh[i][j] %= mod;
    }
  }

  auto qsum = [&](int x1, int y1, int x2, int y2) {
    int x;
    if (x1 == 0 && y1 == 0) {
      x = hsh[x2][y2];
    } else if (x1 == 0) {
      x = hsh[x2][y2] - hsh[x2][y1 - 1];
    } else if (y1 == 0) {
      x = hsh[x2][y2] - hsh[x1 - 1][y2];
    } else
      x = hsh[x2][y2] - hsh[x2][y1 - 1] - hsh[x1 - 1][y2] + hsh[x1 - 1][y1 - 1];

    x %= mod;
    x += mod;
    return x % mod;
  };

  auto valh = [&](int x, int y, int len) {
    int rows = len / m;

    int val = 0;
    if (rows > 0) {
      val += qsum(x, y, x + rows - 1, y + m - 1);
    }
    if (len % m != 0) {
      val += qsum(x + rows, y, x + rows, y + len % m - 1);
    }
    val %= mod;
    return val * powvi[(n - 1 - x) * m + (m - 1 - y)] % mod;
  };

  int minx = 0, miny = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      int l = 1, r = n * m;
      while (l < r) {
        int mid = (l + r) / 2;
        if (valh(minx, miny, mid) == valh(i, j, mid)) {
          l = mid + 1;
        } else {
          r = mid;
        }
      }

      l--;

      if (vvi[i + (l / m)][j + (l % m)] == '*') {
        // cout << minx << " " << miny << " " << i << " " << j << " " << l <<
        // "\n";
        minx = i, miny = j;
      }
    }
  }

  // for (int i = 0; i < hsh.size(); i++) {
  //   for (int j = 0; j < hsh[i].size(); j++) {
  //     cout << hsh[i][j] << " ";
  //   }
  //   cout << "\n";
  // }
  //
  // cout << valh(0, 0, 1) << " " << valh(0, 1, 1) << "\n";

  for (int i = minx; i < minx + n; i++) {
    for (int j = miny; j < miny + m; j++) {
      cout << vvi[i][j];
    }
    cout << "\n";
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60