이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |