oj.uz

답안 #121523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121523 2019-06-26T16:53:16 Z OptxPrime Ispit (COCI19_ispit) C++11
90 / 90
 288 ms 55080 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][510][26];
long long h[510][510];
bool is[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; }       /// odsad samo ovaj mod koristiti!!!!!!!!!!!!!

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++ ){
        is[i]=false;
        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++ ){
                is[i]=true;
                num[i][0][j]=0;
            for( int pos=1;pos<=n;pos++ ){
                num[i][pos][j] = num[i][pos-1][j]+  ( s[pos-1] == char( 'a'+j ) ); /// pos-1 jer je 1-indexiran pos
            }
        }
        h[i][1]=s[0];
        for( int j=2;j<=n;j++ ) h[i][j] = ((( h[i][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. retardiran sam, racunam hash puno puta i zato je tle
                string s=st[dokle];
        if( !is[dokle] ){
                is[dokle]=true;
            for( int j=0;j<26;j++ ){
                num[dokle][0][j]=0;
            for( int pos=1;pos<=n;pos++ ){
                num[dokle][pos][j] = num[dokle][pos-1][j]+  ( s[pos-1] == char( 'a'+j ) ); /// pos-1 jer je 1-indexiran pos
            }
        }
         h[dokle][1]=s[0];
        for( int j=2;j<=n;j++ ) h[dokle][j] = ((( h[dokle][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[i][mid] == h[dokle][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
                /// doraditi ovo, tmph
            mid=lo+(hi-lo)/2;
            long long val1 = ( h[i][n]-((h[i][mid-1]*p[n-mid+1])%b));
            long long val2=( h[dokle][n]-((h[dokle][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[i][suff-1][j]- num[i][pref][j] != num[dokle][suff-1][j]-num[dokle][pref][j] ){
                is=false;
                break;
            }
        }
        if( is ){
            cout<<"DA"<<endl;
            return 0;
        }
        }
    }
        cout <<"NE"<<endl;

    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 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 256 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 10240 KB Output is correct
2 Correct 23 ms 10240 KB Output is correct
3 Correct 33 ms 10280 KB Output is correct
4 Correct 28 ms 10240 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 10240 KB Output is correct
2 Correct 29 ms 10360 KB Output is correct
3 Correct 35 ms 10240 KB Output is correct
4 Correct 31 ms 10240 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 10360 KB Output is correct
2 Correct 26 ms 10240 KB Output is correct
3 Correct 35 ms 10240 KB Output is correct
4 Correct 30 ms 10212 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 10240 KB Output is correct
2 Correct 15 ms 10240 KB Output is correct
3 Correct 34 ms 10240 KB Output is correct
4 Correct 33 ms 10240 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 54760 KB Output is correct
2 Correct 166 ms 54904 KB Output is correct
3 Correct 288 ms 55032 KB Output is correct
4 Correct 172 ms 55032 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 54780 KB Output is correct
2 Correct 110 ms 55080 KB Output is correct
3 Correct 204 ms 55032 KB Output is correct
4 Correct 198 ms 55056 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 54760 KB Output is correct
2 Correct 89 ms 54952 KB Output is correct
3 Correct 207 ms 55072 KB Output is correct
4 Correct 170 ms 55052 KB Output is correct