oj.uz

답안 #572676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -