Submission #28252

#	Time	Username	Problem	Language	Result	Execution time	Memory
28252		Official Fan of ACG (#68)	Play Onwards (FXCUP2_onward)	C++14	1 / 1	249 ms	2296 KiB

onward

#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

bool cmp(const string& A, const string& B, int K) {
	for (int i = 0; i < A.size(); i++) for (int j = 0; j < B.size(); j++) {
		bool cur = true;
		for (int k = 0; k < K; k++) {
			if (i + k >= A.size() || j + k >= B.size() || A[i + k] != B[j + k]) cur = false;
		}
		if (cur) return true;
	}
	return false;
}

string in[200];
vector<int> g[200];

int ans[200];
void dfs(int u) {
	for (int v : g[u]) if (!ans[v]) {
		ans[v] = 3 - ans[u];
		dfs(v);
	}
}

int main() {
	int N, K; cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> in[i];
	for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) {
		if (cmp(in[i], in[j], K)) {
			g[i].push_back(j);
			g[j].push_back(i);
		}
	}

	int cur = 1;
	for (int i = 0; i < N; i++) if (!ans[i]) {
		ans[i] = cur;
		dfs(i);
		cur = 3 - cur;
	}

	for (int i = 0; i < N; i++) for (int j : g[i]) if (ans[i] == ans[j]) {
		cout << "No";
		return 0;
	}

	vector<int> A, B;
	for (int i = 0; i < N; i++) if (ans[i] == 1) A.push_back(i); else B.push_back(i);

	if (A.empty() || B.empty()) {
		cout << "No";
		return 0;
	}

	cout << "Yes" << endl;
	for (int i = 0; i < N; i++) cout << ans[i] << endl;
}

Compilation message (stderr)

onward.cpp: In function 'bool cmp(const string&, const string&, int)':
onward.cpp:9:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); i++) for (int j = 0; j < B.size(); j++) {
                    ^
onward.cpp:9:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); i++) for (int j = 0; j < B.size(); j++) {
                                                       ^
onward.cpp:12:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i + k >= A.size() || j + k >= B.size() || A[i + k] != B[j + k]) cur = false;
              ^
onward.cpp:12:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i + k >= A.size() || j + k >= B.size() || A[i + k] != B[j + k]) cur = false;
                                   ^

• Subtask 1: 1 / 1