제출 #1299881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299881		alan_c	Sateliti (COCI20_satellti)	C++20	0 / 110	2 ms	1084 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll M = (1ll << 61) - 1, R = uniform_int_distribution<ll>(0, M - 1)(rng);

array<ll, N> h[N], hhash[N], pows;

ll sub(array<ll, N> &a, int l, int r) {
  return (ll)((a[r] - (__int128)pows[r - l + 1] * a[l - 1]) % M);
}

int bin_search(int l, int r, function<bool(int)> f) {
  while (l < r) {
    int m = (l + r + 1) / 2;
    if (f(m))
      l = m;
    else
      r = m - 1;
  }
  return l;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<string> image(n);
  for (auto &s : image)
    cin >> s;

  pows[0] = 1;
  for (int i = 1; i < N; i++)
    pows[i] = (ll)((__int128)R * pows[i - 1] % M);

  for (int i = 1; i < 2 * n; i++) {
    for (int j = 1; j < 2 * m; j++)
      h[i][j] =
          (ll)(((__int128)R * h[i][j - 1] + image[(i - 1) % n][(j - 1) % m]) %
               M);
    for (int j = 1; j <= m; j++)
      hhash[j][i] =
          (ll)(((__int128)R * hhash[j][i - 1] + sub(h[i], j, j + m - 1)) % M);
  }

  int r = 0, c = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      int rsame = bin_search(0, n, [&](int mid) {
        return sub(hhash[c + 1], r + 1, r + mid) ==
               sub(hhash[j + 1], i + 1, i + mid);
      });
      if (rsame == n)
        continue;

      int csame = bin_search(0, n, [&](int mid) {
        return sub(h[r + rsame + 1], c + 1, c + mid) ==
               sub(h[i + rsame + 1], j + 1, j + mid);
      });

      if (image[(r + rsame) % n][(c + csame) % m] >
          image[(i + rsame) % n][(j + csame) % m]) {
        r = i;
        c = j;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++)
      cout << image[(r + i) % n][(c + j) % m];
    cout << '\n';
  }
}

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