Submission #501960

#	Time	Username	Problem	Language	Result	Execution time	Memory
501960		SSRS	Sateliti (COCI20_satellti)	C++14	10 / 110	35 ms	3880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long BASE1 = 123456789;
const long long BASE2 = 987654321;
const long long MOD = 1000000007;
int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<char>> c(n, vector<char>(m));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      cin >> c[i][j];
    }
  }
  vector<long long> POW1(m);
  POW1[0] = 1;
  for (int i = 0; i < m - 1; i++){
    POW1[i + 1] = POW1[i] * BASE1 % MOD;
  }
  vector<long long> POW2(n);
  POW2[0] = 1;
  for (int i = 0; i < n - 1; i++){
    POW2[i + 1] = POW2[i] * BASE2 % MOD;
  }
  vector<vector<long long>> S(n, vector<long long>(m * 2));
  for (int i = 0; i < n; i++){
    S[i][m * 2 - 1] = 0;
    for (int j = m * 2 - 2; j >= 0; j--){
      S[i][j] = (S[i][j + 1] * BASE1 + c[i][j % m]) % MOD;
    }
  }
  vector<vector<long long>> hash(n, vector<long long>(m));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      hash[i][j] = (S[i][j] - S[i][j + m] * POW1[m] % MOD + MOD) % MOD;
    }
  }
  vector<vector<long long>> S2(m, vector<long long>(n * 2));
  for (int i = 0; i < m; i++){
    S2[i][n * 2 - 1] = 0;
    for (int j = n * 2 - 2; j >= 0; j--){
      S2[i][j] = (S2[i][j + 1] * BASE2 + hash[j % n][i]) % MOD;
    }
  }
  int ans_i = 0, ans_j = 0;
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      int tv1 = 0, fv1 = n + 1;
      while (fv1 - tv1 > 1){
        int mid = (tv1 + fv1) / 2;
        long long hash1 = (S2[ans_j][ans_i] - S2[ans_j][ans_i + mid] * POW2[mid] % MOD + MOD) % MOD;
        long long hash2 = (S2[j][i] - S2[j][i + mid] * POW2[mid] % MOD + MOD) % MOD;
        if (hash1 == hash2){
          tv1 = mid;
        } else {
          fv1 = mid;
        }
      }
      if (tv1 < n){
        int r1 = (ans_i + tv1) % n;
        int r2 = (i + tv1) % n;
        int tv2 = 0, fv2 = m;
        while (fv2 - tv2 > 1){
          int mid = (tv2 + fv2) / 2;
          long long hash1 = (S[r1][ans_j] - S[r1][ans_j + mid] * POW1[mid] % MOD + MOD) % MOD;
          long long hash2 = (S[r2][j] - S[r2][j + mid] * POW1[mid] % MOD + MOD) % MOD;
          if (hash1 == hash2){
            tv2 = mid;
          } else {
            fv2 = mid;
          }
        }
        int c1 = (ans_j + tv2) % m;
        int c2 = (j + tv2) % m;
        if (c[r2][c2] < c[r1][c1]){
          ans_i = i;
          ans_j = j;
        }
      }
    }
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      cout << c[(i + ans_i) % n][(j + ans_j) % m];
    }
    cout << endl;
  }
}

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