oj.uz

답안 #97294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97294 2019-02-14T22:08:25 Z IgorBaliuk Ispit (COCI19_ispit) C++14
90 / 90
 1844 ms 1016 KB 
//#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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