oj.uz

Submission #501967

# Submission time Handle Problem Language Result Execution time Memory
501967 2022-01-05T01:16:55 Z SSRS Sateliti (COCI20_satellti) C++14
110 / 110
 514 ms 41496 KB 
#include <bits/stdc++.h>
using namespace std;
const long long BASE1 = 123456789;
const long long BASE2 = 987654321;
const long long MOD = 998244353;
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] = POW1[i] * BASE1 % MOD;
  }
  vector<long long> POW2(n + 1);
  POW2[0] = 1;
  for (int i = 0; i < n; 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.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 2 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 332 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 2 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 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 35 ms 3816 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 34 ms 3832 KB Output is correct
12 Correct 35 ms 3836 KB Output is correct
13 Correct 36 ms 4004 KB Output is correct
14 Correct 35 ms 3948 KB Output is correct
15 Correct 35 ms 3952 KB Output is correct
16 Correct 35 ms 3940 KB Output is correct
17 Correct 36 ms 3964 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 2 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 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 35 ms 3816 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 34 ms 3832 KB Output is correct
12 Correct 35 ms 3836 KB Output is correct
13 Correct 36 ms 4004 KB Output is correct
14 Correct 35 ms 3948 KB Output is correct
15 Correct 35 ms 3952 KB Output is correct
16 Correct 35 ms 3940 KB Output is correct
17 Correct 36 ms 3964 KB Output is correct
18 Correct 467 ms 41348 KB Output is correct
19 Correct 5 ms 844 KB Output is correct
20 Correct 7 ms 1100 KB Output is correct
21 Correct 458 ms 41460 KB Output is correct
22 Correct 494 ms 41468 KB Output is correct
23 Correct 489 ms 41460 KB Output is correct
24 Correct 483 ms 41460 KB Output is correct
25 Correct 451 ms 41496 KB Output is correct
26 Correct 514 ms 41464 KB Output is correct
27 Correct 503 ms 41380 KB Output is correct