Submission #28369

#TimeUsernameProblemLanguageResultExecution timeMemory
28369ㅁㄴㅇㄹ (#68)Play Onwards (FXCUP2_onward)C++98
1 / 1
29 ms2196 KiB
#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[2]={1000000007,1610612741}; const ll hbase=1610612741; ll pow26[mx]={1}; int rep[mx],N,K; int adj[mx][mx], vis[mx]; string S[mx]; 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[2]={0,0}; for(int b=0;b<2;b++){ for(int t=0;t<K;t++){ H[b]=((H[b]*26)%hbase[b]+(S[i][t]-'a'))%hbase[b]; } } Sh.insert(mp(H[0],H[1])); for(int t=K;t<u;t++){ for(int b=0;b<2;b++) H[b]=(((H[b]*26%hbase[b])+(S[i][t]-'a'))%hbase[b]-(S[i][t-K]-'a')+hbase[b])%hbase[b]; Sh.insert(mp(H[0],H[1])); } H[0]=H[1]=0; for(int t=0;t<K;t++){ for(int b=0;b<2;b++) H[b]=((H[b]*26)%hbase[b]+(S[j][t]-'a'))%hbase[b]; } if(Sh.find(mp(H[0],H[1]))!=Sh.end()) return true; for(int t=K;t<v;t++){ for(int b=0;b<2;b++) H[b]=(((H[b]*26%hbase[b])+(S[j][t]-'a'))%hbase[b]-(S[j][t-K]-'a')+hbase[b])%hbase[b]; if(Sh.find(mp(H[0],H[1]))!=Sh.end()) return true; } return false; }*/ void buildpow(){ for(int i=1;i<mx;i++) pow26[i]=pow26[i-1]*26%hbase; } 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')*pow26[K]%hbase)+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')*pow26[K]%hbase)+hbase)%hbase; if(Sh.find(H)!=Sh.end()) return true; } return false; } 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=i+1;j<N;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); } } } } void debug(){ for(int i=0;i<N;i++) cout<<S[i]<<endl; for(int i=0;i<N;i++,puts("")) for(int j=0;j<N;j++) printf("%d ",adj[i][j]); } int main(){ //freopen("input.txt","rt",stdin); buildpow(); 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]); } }

Compilation message (stderr)

onward.cpp: In function 'void input()':
onward.cpp:73:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&N,&K);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...