제출 #121519

#제출 시각아이디문제언어결과실행 시간메모리
121519OptxPrimeIspit (COCI19_ispit)C++11
63 / 90
2064 ms1024 KiB
#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=1000000007; string st[510]; /// BITAN ZADATAK JER SAM OPET VJEZBO HASHING. TAKODJER, OVERFLOWANJE JE BILO CESTO PA SAM DEBAGIRO DOSTA int main() { int n,k; cin>>n>>k; p[0]=1LL; /// ovakva petlja ispod proizvodi da je p[5] negativan. zasto? /// for( int i=1;i<=n;i++ ) p[i]=( p[i-1] * a )%b; for( int i=1;i<=n;i++ ){ p[i]=( p[i-1]*a )%b; p[i]%=b; // cout << i << " " << p[i] << " retarde " <<endl; } 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 /// NIKAD FINO NE IZRACUNA, IZGLEDA DA UVIJEK ISPADA IZ RANGE, NE ZNAM STO // if( i==6 && dokle==8 ) cout << (h[10]-(h[8]*p[2])%b) << " " << (tmph[10] - (h[8]*p[2])%b )<< " lubenica " <<endl; // if( i==6 && dokle==8 ) cout << testval1%b << " " << testval2%b << " " << p[5] << " ee mrcin " <<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) ); // if( i==6 && dokle==8 ) cout << mid << " " << val1<< " " << val2 << " prva " <<endl; while( val1 <0 ) val1+=b; /// ako padnu ispod nule while( val2<0 ) val2+=b; val1%=b; val2%=b; // if( i==6 && dokle==8 ) 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(i==6 && dokle==8 ) cout << pref << " " << suff << " svegat " <<endl; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...