제출 #995623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995623		doducanh	Sateliti (COCI20_satellti)	C++14	110 / 110	504 ms	66388 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=1e3;
string s[maxn+7];
int h[maxn*2+7][maxn*2+7];
int pq_pow[2*maxn+7][2*maxn+7];
int n,m;
int add(int a,int b){return (a+b)%mod;}
int sub(int a,int b){return add(a,mod-b);}
int mul(int a,int b){return 1ll*a*b%mod;}
void precalc()
{
    for(int i=1;i<=2*maxn;i++){
        for(int j=1;j<=2*maxn;j++){
            if(i==1&&j==1)pq_pow[i][j]=1;
            else if(i==1)pq_pow[i][j]=mul(pq_pow[i][j-1],2);
            else pq_pow[i][j]=mul(pq_pow[i-1][j],3);
        }
    }
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*m;j++){
            int x=i,y=j;
            if(x>n)x=x-n;
            if(y>m)y=y-m;
            int val=mul(s[x][y]=='.',pq_pow[i][j]);
            h[i][j]=sub(add(add(h[i][j-1],h[i-1][j]),val),h[i-1][j-1]);
        }
    }
}
int get_h(int xo,int yo,int xt,int yt)
{
    return sub(add(h[xt][yt],h[xo-1][yo-1]),add(h[xo-1][yt],h[xt][yo-1]));
}
bool is_equal(int x1,int y1,int x2,int y2,int dx,int dy)
{
    int val1=mul(get_h(x1,y1,x1+dx-1,y1+dy-1),pq_pow[x2][y2]);
    int val2=mul(get_h(x2,y2,x2+dx-1,y2+dy-1),pq_pow[x1][y1]);
    return val1==val2;
}
main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    precalc();
    int solx=1,soly=1;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            int lo_dx=1,hi_dx=n;
            int res=-1;
            while(lo_dx<=hi_dx){
                int mid=(lo_dx+hi_dx)/2;
                if(!is_equal(solx,soly,x,y,mid,m)){
                    res=mid;
                    hi_dx=mid-1;
                }
                else lo_dx=mid+1;
            }
            if(res==-1)continue;
            int dx=res;
            int lo_dy=1,hi_dy=m;
            res=-1;
            while(lo_dy<=hi_dy){
                int mid=(lo_dy+hi_dy)/2;
                if(!is_equal(solx+dx-1,soly,x+dx-1,y,1,mid)){
                    res=mid;
                    hi_dy=mid-1;
                }
                else lo_dy=mid+1;
            }
            if(res==-1)continue;
            int dy=res;
            int i=x+dx-1,j=y+dy-1,u=solx+dx-1,v=soly+dy-1;
            if(i>n)i-=n;
            if(j>m)j-=m;
            if(u>n)u-=n;
            if(v>m)v-=m;
            if(s[i][j]<s[u][v]){
                solx=x;
                soly=y;
            }
        }
    }
//    cout<<get_h(1,2,1,4)<<"\n";
//    cout<<get_h(2,2,2,4)<<"\n";
//    cout<<solx<<" "<<soly<<"\n";
//    cout<<get_h(2,2,2+3-1,2+1-1)<<"\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int x=solx+i,y=soly+j;
            if(x>n)x=x-n;
            if(y>m)y=y-m;
            cout<<s[x][y];
        }
        cout<<"\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60