Submission #111937

#	Time	Username	Problem	Language	Result	Execution time	Memory
111937		fredbr	Ispit (COCI19_ispit)	C++17	90 / 90	131 ms	27604 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

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 pre[maxn];

void init() {
    pre[0] = 1;
    for (int i = 1; i < maxn; i++)
        pre[i] = static_cast<int64_t>(pre[i-1])*p1%mod;
}

void h(char* a, int n, int* v) {
    v[0] = a[0];
    for (int i = 1; i < n; i++)
        v[i] = (static_cast<int64_t>(v[i-1]) + 
                static_cast<int64_t>(pre[i]) * 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);
    
    init();

    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));

                if (!ok) continue;
                ok &= (hc(hs[i], r+1, n-1) == hc(hs[j], r+1, n-1));

                if (!ok) continue;

                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: 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