| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28309 | ㅁㄴㅇㄹ (#68) | Play Onwards (FXCUP2_onward) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define va first
#define vb second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
using namespace std;
const int mx=205;
const ll hbase=1000000007;
int rep[mx],N,K;
int adj[mx][mx], vis[mx];
string S[mx];
unordered_set<ll> Sh;
bool compare(int i, int j){
Sh.clear();
int u=sz(S[i]), v=sz(S[j]);
if(K>min(u,v)) return false;
ll H=0;
for(int t=0;t<K;t++){
H=((H*26)%hbase+(S[i][t]-'a'))%hbase;
}
Sh.insert(H);
for(int t=K;t<u;t++){
H=(((H*26%hbase)+(S[i][t]-'a'))%hbase-(S[i][t-K]-'a')+hbase)%hbase;
Sh.insert(H);
}
H=0;
for(int t=0;t<K;t++){
H=((H*26)%hbase+(S[j][t]-'a'))%hbase;
}
if(Sh.find(H)!=Sh.end()) return true;
for(int t=K;t<v;t++){
H=(((H*26%hbase)+(S[j][t]-'a'))%hbase-(S[j][t-K]-'a')+hbase)%hbase;
if(Sh.find(H)!=Sh.end()) return true;
}
return false;
}
void sep(int i,int j){
}
void input(){
scanf("%d %d\n",&N,&K);
for(int i=0;i<N;i++){
getline(cin,S[i]);
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i!=j) adj[i][j]=adj[j][i]=compare(i,j);
}
}
}
void dfs(int x, int tg){
for(int u=0;u<N;u++){
if(adj[x][u]){
if(vis[u]==tg) exit(0*puts("No"));
if(!vis[u]){
vis[u]=3-tg;
dfs(u,3-tg);
}
}
}
}
int main(){
input();
int tg=1;
for(int i=0;i<N;i++){
if(!vis[i]){
vis[i]=tg;
dfs(i,tg);
}
tg=3-tg;
}
bool flag=true;
for(int i=0;i<N;i++){
flag=flag&&(vis[i]==vis[0]);
}
if(flag) return 0*puts("No");
puts("Yes");
for(int i=0;i<N;i++){
printf("%d\n",vis[i]);
}
}