oj.uz

Submission #501966

# Submission time Handle Problem Language Result Execution time Memory
501966 2022-01-05T01:16:03 Z SSRS Sateliti (COCI20_satellti) C++14
110 / 110
 577 ms 42492 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 38 ms 3908 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 46 ms 4036 KB Output is correct
12 Correct 41 ms 3888 KB Output is correct
13 Correct 38 ms 4036 KB Output is correct
14 Correct 40 ms 4044 KB Output is correct
15 Correct 40 ms 4036 KB Output is correct
16 Correct 40 ms 4044 KB Output is correct
17 Correct 40 ms 4024 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 38 ms 3908 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 46 ms 4036 KB Output is correct
12 Correct 41 ms 3888 KB Output is correct
13 Correct 38 ms 4036 KB Output is correct
14 Correct 40 ms 4044 KB Output is correct
15 Correct 40 ms 4036 KB Output is correct
16 Correct 40 ms 4044 KB Output is correct
17 Correct 40 ms 4024 KB Output is correct
18 Correct 529 ms 42332 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 8 ms 1100 KB Output is correct
21 Correct 533 ms 42492 KB Output is correct
22 Correct 562 ms 42444 KB Output is correct
23 Correct 513 ms 42492 KB Output is correct
24 Correct 534 ms 42492 KB Output is correct
25 Correct 520 ms 42436 KB Output is correct
26 Correct 540 ms 42440 KB Output is correct
27 Correct 577 ms 42356 KB Output is correct