| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 121520 |
2019-06-26T16:19:47 Z |
OptxPrime |
Ispit (COCI19_ispit) |
C++11 |
|
2000 ms |
1100 KB |
#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
/// 63/90 DOBIO, OSTALI TLE. PROBAT OPTIMIZOVAT
long mod(long a, long b)
{ return (a%b+b)%b; }
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) );
val1=mod( val1,b );
val2=mod( val2,b );
// if( i==6 && dokle==8 ) cout << mid << " " << val1<< " " << val2 << " prva " <<endl;
// while( val1 <0 ) val1+=b; /// ako padnu ispod nule.. BOJIM SE DA JE OVDJE TLE, JEL TO MOGUCE??
// 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 time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
512 KB |
Output is correct |
| 2 |
Correct |
159 ms |
560 KB |
Output is correct |
| 3 |
Correct |
302 ms |
512 KB |
Output is correct |
| 4 |
Correct |
228 ms |
560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
564 KB |
Output is correct |
| 2 |
Correct |
238 ms |
524 KB |
Output is correct |
| 3 |
Correct |
307 ms |
512 KB |
Output is correct |
| 4 |
Correct |
306 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
632 KB |
Output is correct |
| 2 |
Correct |
202 ms |
520 KB |
Output is correct |
| 3 |
Correct |
301 ms |
484 KB |
Output is correct |
| 4 |
Correct |
255 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
556 KB |
Output is correct |
| 2 |
Correct |
39 ms |
512 KB |
Output is correct |
| 3 |
Correct |
306 ms |
524 KB |
Output is correct |
| 4 |
Correct |
295 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
1024 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
1024 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2025 ms |
1100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
