oj.uz

Submission #97337

# Submission time Handle Problem Language Result Execution time Memory
97337 2019-02-15T09:48:17 Z szawinis Ispit (COCI19_ispit) C++17
0 / 90
 11 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD1 = 1e9+7, MOD2 = 1e9+9, LINF = 1e18 + 1e16;
const long P1 = 659, P2 = 661;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 
class TaskC {
    int n, k, cnt[501][26];
    string s[501];
public:
    void solve(istream &cin, ostream &cout) {
        cin >> n >> k;
        for(int i = 0; i < n; i++) cin >> s[i];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < k; j++) {
                ++cnt[i][s[i][j] - 'a'];
            }
            for(int ii = 0; ii < i; ii++) {
                bool valid = true;
                for(int j = 0; j < 26; j++) {
                    valid &= cnt[i][j] == cnt[ii][j];
                }
                if(valid) {
                    cout << "DA" << endl;
                    return;
                }
            }
        }
        for(int shift = 1; shift < n - k + 1; shift++) {
            set<pair<long,long> > st;
            for(int i = 0; i < n; i++) {
                long h1 = 0, h2 = 0;
                long pow1 = 1, pow2 = 1;
                for(int j = 0; j < 26; j++, pow1 = pow1 * P1 % MOD1, pow2 = pow2 * P2 % MOD2) {
                    cnt[i][j] += (s[i][shift + k - 1] - 'a' == j) - (s[i][shift - 1] - 'a' == j);
//                    cout << shift << ' ' << i << ' ' << j << ' ' << cnt[i][j] << endl;
                    h1 += cnt[i][j] * pow1;
                    h2 += cnt[i][j] * pow2;
                    h1 %= MOD1;
                    h2 %= MOD2;
                }
                if(st.count(make_pair(h1, h2))) {
                    cout << "DA" << endl;
                    return;
                }
                st.emplace(h1, h2);
            }
        }
        cout << "NE" << endl;
    }
};
 
class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        TaskC *obj = new TaskC();
        obj->solve(in, out);
        delete obj;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Subtask #1
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 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 3 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 3 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Incorrect 8 ms 768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Incorrect 5 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 640 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Incorrect 7 ms 768 KB Output isn't correct
4 Halted 0 ms 0 KB -