Submission #501966

#	Time	Username	Problem	Language	Result	Execution time	Memory
501966		SSRS	Sateliti (COCI20_satellti)	C++14	110 / 110	577 ms	42492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long M30 = ((long long) 1 << 30) - 1;
const long long M31 = ((long long) 1 << 31) - 1;
const long long MOD = ((long long) 1 << 61) - 1;
const long long BASE1 = 1111111;
const long long BASE2 = 1234567;
unsigned long long modulo(unsigned long long x){
  unsigned long long xu = x >> 61;
  unsigned long long xd = x & MOD;
  unsigned long long res = xu + xd;
  if (res >= MOD){
    res -= MOD;
  }
  return res;
}
unsigned long long mul(unsigned long long a, unsigned long long b){
  unsigned long long au = a >> 31;
  unsigned long long ad = a & M31;
  unsigned long long bu = b >> 31;
  unsigned long long bd = b & M31;
  unsigned long long mid = au * bd + ad * bu;
  unsigned long long midu = mid >> 30;
  unsigned long long midd = mid & M30;
  return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
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 + 1);
  POW1[0] = 1;
  for (int i = 0; i < m; i++){
    POW1[i + 1] = mul(POW1[i], BASE1);
  }
  vector<long long> POW2(n + 1);
  POW2[0] = 1;
  for (int i = 0; i < n; i++){
    POW2[i + 1] = mul(POW2[i], BASE2);
  }
  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] = modulo(mul(S[i][j + 1], BASE1) + c[i][j % m]);
    }
  }
  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] = modulo(S[i][j] - mul(S[i][j + m], POW1[m]) + 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] = modulo(mul(S2[i][j + 1], BASE2) + hash[j % n][i]);
    }
  }
  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 = modulo(S2[ans_j][ans_i] - mul(S2[ans_j][ans_i + mid], POW2[mid]) + MOD);
        long long hash2 = modulo(S2[j][i] - mul(S2[j][i + mid], POW2[mid]) + 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 = modulo(S[r1][ans_j] - mul(S[r1][ans_j + mid], POW1[mid]) + MOD);
          long long hash2 = modulo(S[r2][j] - mul(S[r2][j + mid], POW1[mid]) + 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: 40 / 40
• Subtask 3: 60 / 60