oj.uz

답안 #1094202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094202 2024-09-29T00:29:17 Z hippo123 Sateliti (COCI20_satellti) C++17
0 / 110
 3000 ms 48012 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<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; 
		}
	}
}

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;
			d[i][j]=s;			
			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+m-1);
				ll temp2=hashval(pos.f, pos.s, pos.f+mid-1, pos.s+m-1);
				if(temp==temp2) lft=mid+1; 
				else {ans=mid; rht=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)) {
					lft=mid+1 ;
				}
				else { 
					 ans2=mid; rht=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]=='.') cout<<'.';
			else cout<<'*';
		}
		cout<<endl;
	}

}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47964 KB Output is correct
2 Correct 23 ms 47892 KB Output is correct
3 Correct 23 ms 47948 KB Output is correct
4 Correct 22 ms 48012 KB Output is correct
5 Correct 23 ms 47964 KB Output is correct
6 Correct 23 ms 47964 KB Output is correct
7 Execution timed out 3040 ms 47960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47964 KB Output is correct
2 Correct 23 ms 47892 KB Output is correct
3 Correct 23 ms 47948 KB Output is correct
4 Correct 22 ms 48012 KB Output is correct
5 Correct 23 ms 47964 KB Output is correct
6 Correct 23 ms 47964 KB Output is correct
7 Execution timed out 3040 ms 47960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47964 KB Output is correct
2 Correct 23 ms 47892 KB Output is correct
3 Correct 23 ms 47948 KB Output is correct
4 Correct 22 ms 48012 KB Output is correct
5 Correct 23 ms 47964 KB Output is correct
6 Correct 23 ms 47964 KB Output is correct
7 Execution timed out 3040 ms 47960 KB Time limit exceeded
8 Halted 0 ms 0 KB -