oj.uz

Submission #572676

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

const int Nmax=2010;
const ull P=998244353, Q=1e11+19;
int N, M;
bool A[Nmax][Nmax];
ull Pm[Nmax], Qm[Nmax], Pi, Qi, Pim[Nmax], Qim[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*Pim[sx-1]*Qim[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*max(N, M); i++) {
        Pm[i]=Pm[i-1]*P;
        Qm[i]=Qm[i-1]*Q;
    }
    Pi=Pow(P, ULLONG_MAX); Qi=Pow(Q, ULLONG_MAX);
    Pim[0]=Qim[0]=1;
    for(int i=1; i<=2*max(N, M); i++) {
        Pim[i]=Pim[i-1]*Pi;
        Qim[i]=Qim[i-1]*Qi;
    }
    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 3 ms 980 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 6 ms 992 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 6 ms 992 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 288 ms 7244 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 3 ms 3924 KB Output is correct
11 Correct 247 ms 7352 KB Output is correct
12 Correct 246 ms 7464 KB Output is correct
13 Correct 292 ms 7580 KB Output is correct
14 Correct 265 ms 7584 KB Output is correct
15 Correct 304 ms 7600 KB Output is correct
16 Correct 271 ms 7588 KB Output is correct
17 Correct 278 ms 7628 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 6 ms 992 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 288 ms 7244 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 3 ms 3924 KB Output is correct
11 Correct 247 ms 7352 KB Output is correct
12 Correct 246 ms 7464 KB Output is correct
13 Correct 292 ms 7580 KB Output is correct
14 Correct 265 ms 7584 KB Output is correct
15 Correct 304 ms 7600 KB Output is correct
16 Correct 271 ms 7588 KB Output is correct
17 Correct 278 ms 7628 KB Output is correct
18 Execution timed out 3065 ms 44488 KB Time limit exceeded
19 Halted 0 ms 0 KB -