Submission #97294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97294	2019-02-14T22:08:25 Z	IgorBaliuk	Ispit (COCI19_ispit)	C++14	90 / 90	1844 ms	1016 KB

ispit

//#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.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	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct

Subtask #2
9.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	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	396 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	512 KB	Output is correct
2	Correct	64 ms	384 KB	Output is correct
3	Correct	94 ms	384 KB	Output is correct
4	Correct	126 ms	512 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	384 KB	Output is correct
2	Correct	61 ms	480 KB	Output is correct
3	Correct	100 ms	384 KB	Output is correct
4	Correct	85 ms	472 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	384 KB	Output is correct
2	Correct	57 ms	504 KB	Output is correct
3	Correct	71 ms	512 KB	Output is correct
4	Correct	94 ms	632 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	504 KB	Output is correct
2	Correct	59 ms	476 KB	Output is correct
3	Correct	107 ms	512 KB	Output is correct
4	Correct	86 ms	512 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	785 ms	896 KB	Output is correct
2	Correct	735 ms	916 KB	Output is correct
3	Correct	953 ms	896 KB	Output is correct
4	Correct	1077 ms	896 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	720 ms	916 KB	Output is correct
2	Correct	762 ms	1016 KB	Output is correct
3	Correct	1844 ms	896 KB	Output is correct
4	Correct	1464 ms	896 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	747 ms	896 KB	Output is correct
2	Correct	748 ms	948 KB	Output is correct
3	Correct	1238 ms	1016 KB	Output is correct
4	Correct	1153 ms	964 KB	Output is correct

Submission #97294

Compilation message