oj.uz

답안 #111937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111937 2019-05-16T21:24:35 Z fredbr Ispit (COCI19_ispit) C++17
90 / 90
 131 ms 27604 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 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 256 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 428 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5760 KB Output is correct
2 Correct 8 ms 5768 KB Output is correct
3 Correct 12 ms 5760 KB Output is correct
4 Correct 12 ms 5760 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5760 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 10 ms 5760 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5760 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5760 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 9 ms 5732 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27260 KB Output is correct
2 Correct 31 ms 27256 KB Output is correct
3 Correct 39 ms 27264 KB Output is correct
4 Correct 37 ms 27256 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 27260 KB Output is correct
2 Correct 29 ms 27264 KB Output is correct
3 Correct 131 ms 27384 KB Output is correct
4 Correct 124 ms 27604 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 27256 KB Output is correct
2 Correct 34 ms 27256 KB Output is correct
3 Correct 73 ms 27264 KB Output is correct
4 Correct 71 ms 27256 KB Output is correct