제출 #1011815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011815		vjudge1	Sateliti (COCI20_satellti)	C++17	110 / 110	746 ms	22024 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2000 + 5, p = 727, q = 311, mod = 1'000'000'009;
char M[N][N];
int pwp[N], pwq[N], invp[N], invq[N], n, m;
int hsh[N][N];

int charhash(char c, int i, int j) {
  ll ans = c;
  ans = ans * pwp[i] % mod;
  ans = ans * pwq[j] % mod;
  return ans;
}

ll pw(int a, int b)
{
  if(!b) return 1;
  ll ans = pw(a, b / 2);
  ans = ans * ans % mod;
  if(b & 1) ans = ans * a % mod;
  return ans;
}

int gethash(int x1, int y1, int x2, int y2)
{
  ll ans = 1ll * (hsh[x2][y2] + hsh[x1][y1]) % mod - (hsh[x1][y2] + hsh[x2][y1]) % mod;
  ans = (ans % mod + mod) % mod;
  ans = ans * invp[x1] % mod;
  ans = ans * invq[y1] % mod;
  return ans;
}

void preprocess()
{
  pwp[0] = 1;
  for(int i = 1; i <= 2 * n; i ++)
    pwp[i] = 1ll * pwp[i - 1] * p % mod;

  pwq[0] = 1;
  for(int i = 1; i <= 2 * m; i ++)
    pwq[i] = 1ll * pwq[i - 1] * q % mod;

  invp[2 * n] = pw(pwp[2 * n], mod - 2);
  invq[2 * m] = pw(pwq[2 * m], mod - 2);

  for(int i = 2 * n - 1; i >= 0; i--)
    invp[i] = 1ll * invp[i + 1] * p % mod;

  for(int i = 2 * m - 1; i >= 0; i--)
    invq[i] = 1ll * invq[i + 1] * q % mod;
  
  for(int i = 0; i < 2 * n; i ++)
    for(int j = 0; j < 2 * m; j++)
      hsh[i + 1][j + 1] = ((1ll * charhash(M[i][j], i, j) + hsh[i + 1][j] + hsh[i][j + 1] - hsh[i][j]) % mod + mod) % mod;
}

bool Less(pair<int,int> p1, pair<int,int> p2)
{
  int x1 = p1.first, y1 = p1.second;
  int x2 = p2.first, y2 = p2.second;
  if(gethash(x1, y1, x1 + n, y1 + m) == gethash(x2, y2, x2 + n, y2 + m)) return false;

  int l = 0, r = n;
  while(r - l > 1)
    {
      int mid = (l + r) / 2;
      if(gethash(x1, y1, x1 + mid, y1 + m) == gethash(x2, y2, x2 + mid, y2 + m))
	l = mid;
      else
	r = mid;
    }
  int r1 = x1 + l, r2 = x2 + l;

  l = 0, r = m;

  while(r - l > 1)
    {
      int mid = (l + r) / 2;
      if(gethash(r1, y1, r1 + 1, y1 + mid) == gethash(r2, y2, r2 + 1, y2 + mid))
	l = mid;
      else
	r = mid;
    }
  int c1 = y1 + l, c2 = y2 + l;
  return M[r1][c1] < M[r2][c2];  
}

int main()
{
  cin >> n >> m;
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++)
      {
	cin >> M[i][j];
	M[n + i][j] = M[i][j + m] = M[n + i][j + m] = M[i][j];
      }

  preprocess();
  pair<int,int> ans = {0, 0};
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j++)
      if(Less(make_pair(i, j), ans))
	  ans = make_pair(i, j);

  for(int i = 0; i < n; i ++)
    {
      for(int j = 0; j < m ; j ++)
	cout << M[i + ans.first][j + ans.second];
      cout << endl;
    }
  return 0;
}

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