제출 #1094200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094200		hippo123	Sateliti (COCI20_satellti)	C++17	10 / 110	107 ms	48216 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second
#define ndim 2010
const ll a =2;
const ll b =3;
const ll mod=(1LL<<60)-1;

int n, m;


vector<ll> pa(ndim);
vector<ll> pb(ndim);

vector<vector<ll>> hs(ndim, vector<ll> (ndim));

vector<vector<int>> d(ndim, vector<int> (ndim));

static __int128 mul(ll a, ll b) {return (__int128) a*b;}
static ll mod_mul(ll a, ll b, ll mod) { return mul(a, b)%mod;}


void hashfun(){
	pa[0]=1;
	for (int i=0; i<2001; i++) pa[i+1]=mod_mul(pa[i], a, mod);
	pb[0]=1;
	for (int i=0; i<2001; i++) pb[i+1]=mod_mul(pb[i], b, mod);

	hs[0][0]=0;
	for (int i=0; i<2001; i++) {hs[i][0]=0; hs[0][i]=0;}
	for (int i=0; i<2*n; i++){// row
		for (int j=0; j<2*m; j++){
			hs[i+1][j+1]=(mod_mul(hs[i][j+1], a, mod)+mod_mul(hs[i+1][j], b, mod))%mod; 
			hs[i+1][j+1]=((hs[i+1][j+1]-mod_mul(mod_mul(hs[i][j], a, mod), b, mod))%mod+mod)%mod;
			hs[i+1][j+1]=(hs[i+1][j+1]-d[i][j])%mod; 
			//(hsh[i][j] -= hsh[i - 1][j - 1] * base1 * base2 % MOD + a[i][j] - 'a' + 1) %= MOD;
		}
	}
}

ll hashval(int bx, int by, int ex, int ey){
	ll temp=hs[ex+1][ey+1];
	ll temp1=mod_mul(hs[bx][ey+1], pa[ex-bx+1], mod);
	ll temp2=mod_mul(hs[ex+1][by], pb[ey-by+1], mod);
	ll temp3=mod_mul(mod_mul(hs[bx][by], pa[ex-bx+1], mod), pb[ey-by+1], mod);
	
	temp=(((temp-temp1+mod)%mod+mod-temp2)%mod+temp3+mod)%mod;
	return temp;
}

int main(){
	cin>>n>>m;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			char s; cin>>s;
			if(s=='*') d[i][j]=0;
			else d[i][j]=1;
			
			d[i+n][j]=d[i][j]; d[i][j+m]=d[i][j];  d[i+n][j+m]=d[i][j]; 
		}
	}
	hashfun();
	
	pr pos={0, 0}; // initial position
	for (int i=0; i<n; i++){ 
		for (int j=0; j<m; j++){
			//
			//cout<< " i/j= "<<i<<" "<<j<<endl;
			int lft=1; int rht=n; int ans=-1; 
			while(lft<rht){
				int mid=(lft+rht)/2;
				ll temp=hashval(i, j, i+mid-1,j+n-1);
				ll temp2=hashval(pos.f, pos.s, pos.f+mid-1, pos.s+n-1);
				if(!(temp==temp2)) {
					rht=mid; ans=mid; 
				}
				else { 
					 lft=mid+1;
				}	
			
			}
			//cout<<" ans= "<<ans<<endl;
			if(ans==-1) continue;  
			
			lft=1;  rht=m; int ans2=-1; 
			while(lft<rht){
				int mid=(lft+rht)/2; 
				ll temp =hashval(i, j, i+ans-1, j+mid-1);
				ll temp2=hashval(pos.f, pos.s, pos.f+ans-1, pos.s+mid-1);
				
				if(!(temp==temp2)) {
					rht=mid; ans2=mid; 
				}
				else { 
					 lft=mid+1;
				}		

			}
			if(ans2==-1) continue; 
			
			if(d[i+ans-1][j+ans2-1]<d[pos.f+ans-1][pos.s+ans2-1]){
				pos.f=i; pos.s=j; 
			}		
				
		}
		
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++) {
			if(d[i+pos.f][j+pos.s]==1) cout<<'.';
			else cout<<'*';
		}
		cout<<endl;
	}

}

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