oj.uz

Submission #111934

# Submission time Handle Problem Language Result Execution time Memory
111934 2019-05-16T21:14:35 Z fredbr Ispit (COCI19_ispit) C++17
18 / 90
 1941 ms 27404 KB 
#include <bits/stdc++.h>

using namespace std;

struct Prefix {
    int v[26];

    Prefix& operator=(char a) {
        fill(v, v+26, 0);
        v[a-'a']++;
        return *this;
    }

    Prefix& operator+=(Prefix const& rhs) {
        for (int i = 0; i < 26; i++)
            v[i] += rhs.v[i];
        return *this;
    }

    Prefix& operator-=(Prefix const& rhs) {
        for (int i = 0; i < 26; i++)
            v[i] -= rhs.v[i];
        return *this;
    }

    bool operator==(Prefix const& rhs) const {
        return equal(v, v+26, rhs.v, rhs.v+26);
    }
};

int const maxn = 505;
int const mod = 1e9 + 9;
int const p1 = 37;

int fexp(int64_t a, int b, int c) {
    int64_t ans = 1;
    while (b) {
        if (b&1) ans = ans*a%c;
        a = a*a%c;
        b >>= 1;
    }
    return ans;
} 

void h(char* a, int n, int* v) {
    v[0] = a[0];
    for (int i = 1; i < n; i++)
        v[i] = (static_cast<uint64_t>(v[i-1]) + fexp(p1, i, mod)*a[i])%mod;
}

int hc(int* v, int l, int r) {
    int x = v[r];
    if (l > 0) x -= v[l-1];
    if (x < 0) x += mod;

    return x;
}

char v[maxn][maxn];
int hs[maxn][maxn];
Prefix p[maxn][maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> v[i];
        
        for (int j = 0; j < n; j++) {
            p[i][j] = v[i][j];
            if (j > 0)
                p[i][j] += p[i][j-1];
        }

        h(v[i], n, hs[i]);
    }

    bool certo = false;
    for (int l = 0; l < n-k+1; l++) {
        int r = l+k-1;

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {

                
                bool ok = true;

                if (l > 0) ok &= (hc(hs[i], 0, l-1) == hc(hs[j], 0, l-1));
                ok &= (hc(hs[i], r+1, n-1) == hc(hs[j], r+1, n-1));

                Prefix ip = p[i][r], jp = p[j][r];

                if (l > 0) {
                    ip -= p[i][l-1];
                    jp -= p[j][l-1];
                }

                ok &= (ip == jp);

                if (ok) certo = true;
            }
        }
    }

    if (certo) cout << "DA\n";
    else cout << "NE\n";
}

Subtask #1
9.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 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 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

Subtask #3
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 #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5632 KB Output is correct
2 Correct 12 ms 5740 KB Output is correct
3 Correct 77 ms 5760 KB Output is correct
4 Incorrect 63 ms 5752 KB Output isn't correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5760 KB Output is correct
2 Correct 19 ms 5760 KB Output is correct
3 Correct 126 ms 5760 KB Output is correct
4 Incorrect 114 ms 5760 KB Output isn't correct

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 27356 KB Output is correct
2 Correct 163 ms 27404 KB Output is correct
3 Correct 1751 ms 27356 KB Output is correct
4 Incorrect 1941 ms 27332 KB Output isn't correct