oj.uz

답안 #501960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501960 2022-01-05T00:54:45 Z SSRS Sateliti (COCI20_satellti) C++14
10 / 110
 35 ms 3880 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 264 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 268 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 1 ms 288 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 264 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 268 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 34 ms 3880 KB Output is correct
9 Correct 1 ms 412 KB Output is correct
10 Correct 1 ms 268 KB Output is correct
11 Incorrect 35 ms 3868 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 264 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 268 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 272 KB Output is correct
6 Correct 1 ms 284 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 34 ms 3880 KB Output is correct
9 Correct 1 ms 412 KB Output is correct
10 Correct 1 ms 268 KB Output is correct
11 Incorrect 35 ms 3868 KB Output isn't correct
12 Halted 0 ms 0 KB -