oj.uz

Submission #572670

# Submission time Handle Problem Language Result Execution time Memory
572670 2022-06-05T02:37:43 Z byunjaewoo Sateliti (COCI20_satellti) C++17
10 / 110
 3000 ms 7252 KB 
#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;

const int Nmax=2010;
const ull P=998244353, Q=1e9+7;
int N, M;
bool A[Nmax][Nmax];
ull Pm[Nmax], Qm[Nmax], H[Nmax][Nmax];
pair<int, int> X[Nmax*Nmax];

ull Pow(ull a, ull b) {
    if(b==0) return 1;
    ull tmp=Pow(a, b/2);
    tmp*=tmp;
    if(b%2) tmp*=a;
    return tmp;
}

ull Hash2D(int sy, int sx, int ey, int ex) {
    ull res=H[ey][ex]-H[sy-1][ex]-H[ey][sx-1]+H[sy-1][sx-1];
    return res*Pow(Pow(P, ULLONG_MAX), sx-1)*Pow(Pow(Q, ULLONG_MAX), sy-1);
}

ull Hash1D(int y, int sx, int ex) {
    return Hash2D(y, sx, y, ex);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=N; i++) {
        string S; cin>>S;
        for(int j=1; j<=M; j++) A[i][j]=(S[j-1]=='.');
    }
    for(int i=1; i<=N; i++) {
        for(int j=M+1; j<=2*M; j++) A[i][j]=A[i][j-M];
    }
    for(int i=N+1; i<=2*N; i++) {
        for(int j=1; j<=2*M; j++) A[i][j]=A[i-N][j];
    }
    Pm[0]=Qm[0]=1;
    for(int i=1; i<=2*N; i++) {
        Pm[i]=Pm[i-1]*P;
        Qm[i]=Qm[i-1]*Q;
    }
    for(int i=1; i<=2*N; i++) {
        for(int j=1; j<=2*M; j++) {
            H[i][j]=H[i][j-1]+H[i-1][j]-H[i-1][j-1]+A[i][j]*Pm[j-1]*Qm[i-1];
        }
    }
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) X[M*(i-1)+j]={i, j};
    }
    sort(X+1, X+N*M+1, [](pair<int, int> a, pair<int, int> b) {
        int ay=a.first, ax=a.second, by=b.first, bx=b.second;
        int h=0, w=0;
        for(int s=1, e=N-1; s<=e;) {
            int m=(s+e)/2;
            if(Hash2D(ay, ax, ay+m-1, ax+M-1)==Hash2D(by, bx, by+m-1, bx+M-1)) h=m, s=m+1;
            else e=m-1;
        }
        for(int s=1, e=M; s<=e;) {
            int m=(s+e)/2;
            if(Hash1D(ay+h, ax, ax+m-1)==Hash1D(by+h, bx, bx+m-1)) w=m, s=m+1;
            else e=m-1;
        }
        if(h==N-1 && w==M) return false;
        if(w==M) return A[ay+h][ax]<A[by+h][bx];
        return A[ay+h][ax+w]<A[by+h][bx+w];
    });
    for(int i=X[1].first; i<=X[1].first+N-1; i++) {
        for(int j=X[1].second; j<=X[1].second+M-1; j++) {
            if(A[i][j]) cout<<".";
            else cout<<"*";
        }
        cout<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 1168 KB Output is correct
2 Correct 219 ms 980 KB Output is correct
3 Correct 221 ms 980 KB Output is correct
4 Correct 188 ms 980 KB Output is correct
5 Correct 215 ms 980 KB Output is correct
6 Correct 211 ms 1028 KB Output is correct
7 Correct 187 ms 980 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 1168 KB Output is correct
2 Correct 219 ms 980 KB Output is correct
3 Correct 221 ms 980 KB Output is correct
4 Correct 188 ms 980 KB Output is correct
5 Correct 215 ms 980 KB Output is correct
6 Correct 211 ms 1028 KB Output is correct
7 Correct 187 ms 980 KB Output is correct
8 Execution timed out 3064 ms 7252 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 1168 KB Output is correct
2 Correct 219 ms 980 KB Output is correct
3 Correct 221 ms 980 KB Output is correct
4 Correct 188 ms 980 KB Output is correct
5 Correct 215 ms 980 KB Output is correct
6 Correct 211 ms 1028 KB Output is correct
7 Correct 187 ms 980 KB Output is correct
8 Execution timed out 3064 ms 7252 KB Time limit exceeded
9 Halted 0 ms 0 KB -