oj.uz

답안 #1094198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094198 2024-09-29T00:04:31 Z hippo123 Sateliti (COCI20_satellti) C++17
10 / 110
 99 ms 48020 KB 
#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<2*n; i++) pa[i+1]=mod_mul(pa[i], a, mod);
	pb[0]=1;
	for (int i=0; i<2*m; i++) pb[i+1]=mod_mul(pb[i], b, mod);

	hs[0][0]=0;
	for (int i=0; i<max(2*n, 2*m); 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; 
		}
	}
}

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;
				}		

			}
			//cout<<" ans2= "<<ans2<<endl;
			if(ans2==-1) continue; 
			
			// compare the first different char
			//cout<<" d[i+ans-1][j+ans2-1]/d[pos.f+ans-1][pos.s+ans2-1]= "<<d[i+ans-1][j+ans2-1]<<" "<<d[pos.f+ans-1][pos.s+ans2-1]<<endl;
			if(d[i+ans-1][j+ans2-1]<d[pos.f+ans-1][pos.s+ans2-1]){
				pos.f=i; pos.s=j; 
			}		
				
		//cout<<" pos.f/pos.s= "<<pos.f<<" "<<pos.s<<endl;
		}
		
	}
	//cout<<" outside"<<endl;
	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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47976 KB Output is correct
2 Correct 24 ms 48020 KB Output is correct
3 Correct 23 ms 47976 KB Output is correct
4 Correct 23 ms 47976 KB Output is correct
5 Correct 24 ms 47844 KB Output is correct
6 Correct 23 ms 47976 KB Output is correct
7 Correct 24 ms 47976 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47976 KB Output is correct
2 Correct 24 ms 48020 KB Output is correct
3 Correct 23 ms 47976 KB Output is correct
4 Correct 23 ms 47976 KB Output is correct
5 Correct 24 ms 47844 KB Output is correct
6 Correct 23 ms 47976 KB Output is correct
7 Correct 24 ms 47976 KB Output is correct
8 Correct 99 ms 47964 KB Output is correct
9 Incorrect 24 ms 47964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47976 KB Output is correct
2 Correct 24 ms 48020 KB Output is correct
3 Correct 23 ms 47976 KB Output is correct
4 Correct 23 ms 47976 KB Output is correct
5 Correct 24 ms 47844 KB Output is correct
6 Correct 23 ms 47976 KB Output is correct
7 Correct 24 ms 47976 KB Output is correct
8 Correct 99 ms 47964 KB Output is correct
9 Incorrect 24 ms 47964 KB Output isn't correct
10 Halted 0 ms 0 KB -