제출 #114832

#제출 시각아이디문제언어결과실행 시간메모리
114832FrankenweenIspit (COCI19_ispit)C++17
0 / 90
5 ms948 KiB
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #define ull unsigned long long #define pll pair<ll, ll> #define mp make_pair #define ll long long #define pb push_back #define deb(x) cout << #x << " = " << x << endl #define all(x) x.begin(), x.end() #define ld long double const ll mod1 = (ll)1e9 + 7; const ll mod2 = (ll)1e9 + 9; const ll BASE = 47; const ll inf = (ll)1e18; const long double e = 2.718281828459; const long double pi = 3.141592653; const ld EPS = 1e-9; using namespace std; template <class T> istream& operator>>(istream &in, vector<T> &arr) { for (T &cnt : arr) { in >> cnt; } return in; }; void solve() { ll n, k; cin >> n >> k; vector<string> arr(n); cin >> arr; vector<ll> p(27); p[0] = 1; for (int i = 1; i < 27; i++) { p[i] = (p[i - 1] * BASE) % mod1; } vector<ll> h(n); for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) { h[j] += p[arr[j][i] - 'a']; if (h[j] >= mod1) { h[j] -= mod1; } } } for (int i = k - 1; i < n; i++) { set<ll> used; for (auto cnt : h) { if (used.count(cnt) != 0) { cout << "DA"; return; } used.insert(cnt); } if (i + 1 < n) { for (int j = 0; j < n; j++) { h[j] -= p[arr[j][i - k + 1] - 'a']; if (h[j] < 0) { h[j] += mod1; } h[j] += p[arr[j][i + 1] - 'a']; if (h[j] >= mod1) { h[j] -= mod1; } } } } cout << "NE"; } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #else freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cout.precision(30); ll seed = time(0); //cerr << "Seed: " << seed << "\n"; srand(seed); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...