제출 #995623

#제출 시각아이디문제언어결과실행 시간메모리
995623doducanhSateliti (COCI20_satellti)C++14
110 / 110
504 ms66388 KiB
#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()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...