oj.uz

Submission #111933

# Submission time Handle Problem Language Result Execution time Memory
111933 2019-05-16T21:13:51 Z fredbr Ispit (COCI19_ispit) C++17
27 / 90
 2000 ms 27656 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 + 7;
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 3 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 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 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 3 ms 512 KB Output is correct
2 Incorrect 2 ms 504 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 30 ms 5760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5760 KB Output is correct
2 Correct 32 ms 5760 KB Output is correct
3 Correct 116 ms 5760 KB Output is correct
4 Incorrect 123 ms 5744 KB Output isn't correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5760 KB Output is correct
2 Correct 12 ms 5888 KB Output is correct
3 Correct 64 ms 5804 KB Output is correct
4 Incorrect 116 ms 5796 KB Output isn't correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5760 KB Output is correct
2 Correct 22 ms 5760 KB Output is correct
3 Correct 127 ms 5760 KB Output is correct
4 Correct 141 ms 5836 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 27564 KB Output is correct
2 Correct 174 ms 27572 KB Output is correct
3 Correct 471 ms 27656 KB Output is correct
4 Incorrect 556 ms 27512 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 27448 KB Output is correct
2 Correct 58 ms 27528 KB Output is correct
3 Execution timed out 2061 ms 27508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 27596 KB Output is correct
2 Correct 163 ms 27568 KB Output is correct
3 Correct 1781 ms 27640 KB Output is correct
4 Incorrect 1881 ms 27640 KB Output isn't correct