이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
long long p[510];
long long num[510][26], tmp[510][26];
long long h[510], tmph[510];
//long long a=1000000007;
long long a=999999937;
long long b=10000000007;
string st[510];
int main()
{
int n,k;
cin>>n>>k;
p[0]=1;
for( int i=1;i<=n;i++ ) p[i]=( p[i-1] * a )%b;
for( int i=0;i<n;i++ ) cin>>st[i];
for( int i=0;i<n;i++ ){
string s=st[i];
for( int j=0;j<26;j++ ){
num[0][j]=0;
for( int pos=1;pos<=n;pos++ ){
num[pos][j] = num[pos-1][j]+ ( s[pos-1] == char( 'a'+j ) ); /// pos-1 jer je 1-indexiran pos
}
}
h[1]=s[0];
for( int j=2;j<=n;j++ ) h[j] = ((( h[j-1]*a )%b) + s[j-1]%b)%b; /// heshiramo ovaj string
for( int dokle=i+1;dokle<n;dokle++ ){ /// sad kroz sve druge stringove, za svaki nadjemo num i hash
string s=st[dokle];
for( int j=0;j<26;j++ ){
tmp[0][j]=0;
for( int pos=1;pos<=n;pos++ ){
tmp[pos][j] = tmp[pos-1][j]+ ( s[pos-1] == char( 'a'+j ) ); /// pos-1 jer je 1-indexiran pos
}
}
tmph[1]=s[0];
for( int j=2;j<=n;j++ ) tmph[j] = ((( tmph[j-1]*a )%b) + s[j-1]%b)%b; /// heshiramo ovaj string
// if( i==1 && dokle==3 ) cout << h[10]-h[7]*p[2] << " " << tmph[10] - h[7]*p[2] << " lubenica " <<endl;
///sad ide trazenje max prefixa i suffixa i ostalo, binarnom
int lo=1,hi=n,mid,pref=0,suff=n+1;
while( lo<=hi ){ ///prefix
mid=lo+(hi-lo)/2;
if( h[mid] == tmph[mid] ){
lo=mid+1;
pref=max( pref, mid );
}
else hi=mid-1;
}
lo=1,hi=n;
while( lo<=hi ){ ///suffix - TRENUTNO NJEGA NE NADJE DOBRO
mid=lo+(hi-lo)/2;
long long val1 = ( h[n]-((h[mid-1]*p[n-mid+1])%b));
long long val2=( tmph[n]-((tmph[mid-1]*p[n-mid+1])%b) );
while( val1 <0 ) val1+=b; /// ako padnu ispod nule
while( val2<0 ) val2+=b;
val1%=b;
val2%=b;
// if( i==1 && dokle==3 ) cout << mid << " " << val1 << " " << val2 << " rubik " <<endl;
/// cout<< i << " " << dokle << " " << val1 << " " <<val2 << " ramize " << h[n] <<endl;
if( val1==val2 ){
hi=mid-1;
suff=min( suff,mid );
}
else lo=mid+1;
}
if( pref >=suff ){
cout<<"DA"<<endl;
return 0;
}
/// cout << i << " " << dokle << " " <<suff << " " << pref << endl;
//if( i==1 && dokle==3 ) cout << suff << " " << pref << " bosna " <<endl;
if( suff-pref-1 > k ) continue; /// mora biti najvise k razlicitih koje cemo permutirati
// if( i == 1 && dokle == 3 ) cout << " bosna " <<endl;
bool is=true;
for( int j=0;j<26;j++ ){
if( num[suff-1][j]- num[pref][j] != tmp[suff-1][j]-tmp[pref][j] ){
is=false;
break;
}
}
if( is ){
cout<<"DA"<<endl;
return 0;
}
}
}
cout <<"NE"<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |