Submission #238533

#	Time	Username	Problem	Language	Result	Execution time	Memory
238533		DavidDamian	Ispit (COCI19_ispit)	C++11	90 / 90	50 ms	2944 KiB

Main

#include <iostream>
using namespace std;
typedef long long ll;
ll A=37;
ll B=1000000007;
int n,k;
char board[505][505];
ll h[505][505];
ll Pow[505];
void HashStrings()
{
    Pow[0]=1;
    for(int i=1;i<=n;i++){
        Pow[i]=(Pow[i-1]*A) % B;
    }
    for(int i=1;i<=n;i++){
        h[i][0]=board[i][0];
        for(int j=1;j<=n+1;j++){
            h[i][j]=(h[i][j-1]*A + board[i][j]) % B;
        }
    }
}
ll getHash(int i,int a,int b)
{
    if(a==0)
        return h[i][b];
    else{
        ll subtract=h[i][a-1]*Pow[b-a+1];
        subtract%=B;
        ll ans=(h[i][b] + B - subtract) % B;
        return ans;
    }
}
int bucket[505][27];
bool same(int i,int j)
{
    for(int l=0;l<='z'-'a';l++){
        if(bucket[i][l]!=bucket[j][l])
            return false;
    }
    return true;
}
void print()
{
    for(int i=1;i<=n;i++){
        for(int l=0;l<='z'-'a';l++){
            if(bucket[i][l]!=0){
                cout<<i<<" "<<(char)(l+'a')<<" "<<bucket[i][l]<<endl;
            }
        }
    }

}
#define debug(x) cout<<#x<<" = "<<x<<endl
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>board[i][j];
        }
        board[i][0]='a',board[i][n+1]='a';
    }
    HashStrings();
    int a=1,b=k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            bucket[i][ board[i][j]-'a' ]++;
        }
    }
    while(b<=n){
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(getHash(i,0,a-1) != getHash(j,0,a-1)) continue;
                if(getHash(i,b+1,n+1) != getHash(j,b+1,n+1)) continue;
                if(same(i,j)){
                    cout<<"DA\n";
                    return 0;
                }
            }
        }
        for(int i=1;i<=n;i++){
            bucket[i][ board[i][a]-'a' ]--;
        }
        a++;
        b++;
        for(int i=1;i<=n;i++){
            bucket[i][ board[i][b]-'a' ]++;
        }
    }
    cout<<"NE\n";
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9