Submission #111934

#	Time	Username	Problem	Language	Result	Execution time	Memory
111934		fredbr	Ispit (COCI19_ispit)	C++17	18 / 90	1941 ms	27404 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9