oj.uz

Submission #238534

# Submission time Handle Problem Language Result Execution time Memory
238534 2020-06-11T16:36:14 Z DavidDamian Ispit (COCI19_ispit) C++11
90 / 90
 55 ms 2688 KB 
#include <iostream>
using namespace std;
typedef long long ll;
///String Hashing
///Determine if it is possible to form the same word in two rows
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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 9 ms 1280 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 8 ms 1280 KB Output is correct
4 Correct 7 ms 1280 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 8 ms 1280 KB Output is correct
4 Correct 7 ms 1280 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 10 ms 1280 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2688 KB Output is correct
2 Correct 17 ms 2688 KB Output is correct
3 Correct 22 ms 2560 KB Output is correct
4 Correct 16 ms 2560 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2688 KB Output is correct
2 Correct 13 ms 2560 KB Output is correct
3 Correct 55 ms 2680 KB Output is correct
4 Correct 37 ms 2688 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2560 KB Output is correct
2 Correct 17 ms 2688 KB Output is correct
3 Correct 46 ms 2560 KB Output is correct
4 Correct 16 ms 2560 KB Output is correct