# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28252 | 2017-07-16T04:11:28 Z | Official Fan of ACG(#1221, cseteram, 16silver, pps789) | Play Onwards (FXCUP2_onward) | C++14 | 249 ms | 2296 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2032 KB | Output is correct |
2 | Correct | 0 ms | 2032 KB | Output is correct |
3 | Correct | 0 ms | 2032 KB | Output is correct |
4 | Correct | 0 ms | 2032 KB | Output is correct |
5 | Correct | 0 ms | 2296 KB | Output is correct |
6 | Correct | 3 ms | 2296 KB | Output is correct |
7 | Correct | 26 ms | 2032 KB | Output is correct |
8 | Correct | 26 ms | 2032 KB | Output is correct |
9 | Correct | 23 ms | 2032 KB | Output is correct |
10 | Correct | 23 ms | 2032 KB | Output is correct |
11 | Correct | 249 ms | 2032 KB | Output is correct |
12 | Correct | 43 ms | 2032 KB | Output is correct |
13 | Correct | 56 ms | 2032 KB | Output is correct |
14 | Correct | 139 ms | 2032 KB | Output is correct |
15 | Correct | 0 ms | 2032 KB | Output is correct |
16 | Correct | 0 ms | 2032 KB | Output is correct |
17 | Correct | 0 ms | 2032 KB | Output is correct |
18 | Correct | 56 ms | 2032 KB | Output is correct |
19 | Correct | 13 ms | 2032 KB | Output is correct |
20 | Correct | 23 ms | 2032 KB | Output is correct |
21 | Correct | 19 ms | 2032 KB | Output is correct |