oj.uz

Submission #121504

# Submission time Handle Problem Language Result Execution time Memory
121504 2019-06-26T15:23:52 Z OptxPrime Ispit (COCI19_ispit) C++11
9 / 90
 2000 ms 1280 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[1010];
long long num[1010][26], tmp[1010][26];
long long h[1010], tmph[1010];
long long a=1000000007;
long long b=10000000009;
string st[1010];

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;   /// heshiramo ovaj string
        ///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;
    ///       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( suff-pref-1 > k ) continue; /// mora biti najvise k razlicitih koje cemo permutirati
        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;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.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 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 512 KB Output is correct
2 Incorrect 281 ms 584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 596 KB Output is correct
2 Incorrect 289 ms 580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 512 KB Output is correct
2 Correct 201 ms 512 KB Output is correct
3 Correct 323 ms 632 KB Output is correct
4 Incorrect 291 ms 632 KB Output isn't correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 632 KB Output is correct
2 Incorrect 283 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 1280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 1280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 1280 KB Time limit exceeded
2 Halted 0 ms 0 KB -