제출 #1014512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014512		User0069	Sateliti (COCI20_satellti)	C++17	110 / 110	724 ms	80724 KiB

Main

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,a[2005][2005],pfs[2005][2005],po[2005*2005],inv[2005*2005];
int p(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int get(int a,int b,int c,int d)
{
    if(c<a||d<b) return 0;
    return (pfs[c][d]-pfs[c][b-1]-pfs[a-1][d]+pfs[a-1][b-1]+3*mod)%mod;
}
int get1(int i,int j,int k)
{
    int cc=0;
    cc+=get(i,j,i+k/m -1,j+m-1);
//    cout<<cc<<"\n";
    cc+=get(i+k/m,j,i+k/m,j+k%m-1);
//    cout<<cc<<"\n";
    cc%=mod;
    cc*=inv[(i-1)*m+j];
    cc%=mod;
    return cc;
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char x;
            cin>>x;
            if(x=='.') a[i][j]=2;
            else a[i][j]=1;
            a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
        }
    }
    po[0]=1;
    inv[0]=1;
    for(int i=1;i<=n*m;i++)
    {
        po[i]=po[i-1]*31%mod;
        inv[i]=p(po[i],mod-2);
    }
    for(int i=1;i<=2*n;i++)
    {
        for(int j=1;j<=2*m;j++)
        {
            pfs[i][j]=(pfs[i-1][j]+pfs[i][j-1]-pfs[i-1][j-1]+a[i][j]*po[(i-1)*m+j]+3*mod)%mod;
        }
    }
    int bi=1,bj=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int l=1,r=n*m,res=-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(get1(i,j,mid)!=get1(bi,bj,mid))
                {
                    res=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
//            cout<<i<<" "<<j<<" "<<bi<<" "<<bj<<" "<<res<<"\n";
            int ii,jj;
            if(res==-1) continue;
            if(res%m==0)
            {
                ii=res/m-1;
                jj=m-1;
            }
            else
            {
                ii=res/m;
                jj=res%m-1;
            }
//            cout<<i+ii<<" "<<j+jj<<" "<<bi+ii<<" "<<bj+jj<<"!\n";
            if(a[i+ii][j+jj]<a[bi+ii][bj+jj])
            {
                bi=i;
                bj=j;
            }

        }
    }
    for(int i=bi;i<bi+n;i++)
    {
        for(int j=bj;j<bj+m;j++)
        {
            if(a[i][j]==1) cout<<'*';
            else cout<<'.';
        }
        cout<<"\n";
    }
//    cout<<get1(1,2,1)<<" "<<get1(1,1,1);
}

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

Main.cpp: In function 'int main()':
Main.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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