Submission #97337

#	Time	Username	Problem	Language	Result	Execution time	Memory
97337		szawinis	Ispit (COCI19_ispit)	C++17	0 / 90	11 ms	768 KiB

Main

#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
• Subtask 2: 0 / 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