Submission #97294

#	Time	Username	Problem	Language	Result	Execution time	Memory
97294		IgorBaliuk	Ispit (COCI19_ispit)	C++14	90 / 90	1844 ms	1016 KiB

Main

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define endl "\n"
#define mt make_tuple
#define mp make_pair

template <typename T1, typename T2>
bool umax(T1 &a, const T2&b) { return a < b ? a = b, 1 : 0;}
template <typename T1, typename T2> 
bool umin(T1 &a, const T2 &b) {return a > b ? a = b, 1 : 0;}
template <typename T>
T sqr(T a) {return a * a;}

mt19937 rng(20010709);
const int mod = 1000000007;
const int INF = 1000000001;
const int N = 500005;

int n, k;
vector <string> str;
string result = "NE";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	cin >> n >> k;

	str.resize(n);

	for (int i = 0; i < n; i++)
		cin >> str[i];

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			vector <int> prefOk(n), suffOk(n), cnt(128);

			prefOk[0] = str[i][0] == str[j][0];
			suffOk[n - 1] = str[i].back() == str[j].back();

			for (int c = 1; c < n; c++)
				prefOk[c] = prefOk[c - 1] && (str[i][c] == str[j][c]);
			for (int c = n - 2; c > -1; c--)
				suffOk[c] = suffOk[c + 1] && (str[i][c] == str[j][c]);

			int wrong = 0;

			auto modify = [&](char c, int add) {
				bool old = cnt[c] == 0;

				cnt[c] += add;

				if (old != (cnt[c] == 0)) {
					if (cnt[c] == 0)
						wrong--;
					else
						wrong++;
				}
			};

			for (int c = 0; c < k; c++) {
				modify(str[i][c], 1);
				modify(str[j][c], -1);
			}

			if (!wrong && ((k == n) || suffOk[k]))
				result = "DA";

			for (int c = k; c < n; c++) {
				modify(str[i][c - k], -1);
				modify(str[j][c - k], 1);
				modify(str[i][c], 1);
				modify(str[j][c], -1);

				if (!wrong && prefOk[c - k] && ((c + 1 == n) || suffOk[c + 1]))
					result = "DA";
			}
		}
	}

    cout << result << endl;

    return 0;
}

• 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