fork download
copy 
  1. #include<stdio.h>
  2. #include<map>
  3. #include<iostream>
  4. #include<cstring>
  5. #include<memory.h>
  6. #include<algorithm>
  7. using namespace std;
  8. int n,i,j,k,pw,ls,p[5555],pm[5555],vn,exist[5555],mm,an;
  9. string carry;
  10. char dump[2222222],s[2222222];
  11. map<unsigned long long,short>ma;
  12. char f[5555];
  13. unsigned long long hash,words[5555],me;
  14. pair<unsigned long long,string>a[2222222];
  15.  
  16. void spread(int k){
  17. 	int i;
  18. 	for(i=k;i;i=(i-1)&k)if(!exist[i]){
  19. 		exist[i]=1;
  20. 		words[i]=words[k];
  21. 	}
  22. }
  23.  
  24. int main(){
  25. 	freopen("covertexts.in","r",stdin);
  26. 	freopen("covertexts.out","w",stdout);
  27. 	scanf("%d",&n);gets(dump);
  28. 	for(i=1;i<=n;i++){
  29. 		pw=(1<<(i-1));
  30. 		gets(s);ls=strlen(s);carry="";hash=0;
  31. 		for(j=0;j<ls;j++)if(s[j]==' '){
  32. 			if(carry!=""){
  33. 				ma[hash]|=pw;
  34. 				a[++an]=make_pair(hash,carry);
  35. 			}
  36. 			carry="";hash=0;
  37. 		}else{carry+=s[j];hash=hash*239+s[j];}
  38. 		if(carry!=""){
  39. 			ma[hash]|=pw;
  40. 			a[++an]=make_pair(hash,carry);
  41. 		}
  42. 	}
  43. 	for(map<unsigned long long,short>::iterator it=ma.begin();it!=ma.end();it++)if(exist[it->second]==0){
  44. 		words[it->second]=it->first;
  45. 		exist[it->second]=1;
  46. 		spread(it->second);
  47. 	}
  48. 	memset(f,63,sizeof(f));
  49. 	f[0]=0;
  50. 	for(i=0;i<(1<<n);i++)if(f[i]<20){
  51. 		mm=(1<<n)-1-i;
  52. 		for(j=mm;j;j=(j-1)&mm)if(exist[j]&&f[i|j]>f[i]+1){
  53. 			f[i|j]=f[i]+1;
  54. 			p[i|j]=i;
  55. 			pm[i|j]=j;
  56. 		}
  57. 	}
  58. 	printf("%d\n",f[(1<<n)-1]);
  59. 	vn=(1<<n)-1;
  60. 	while(vn){
  61. 		me=words[pm[vn]];
  62. 		for(i=1;i<=an;i++)if(a[i].first==me){
  63. 			cout<<a[i].second<<endl;
  64. 			break;
  65. 		}
  66. //		cout<<words[pm[vn]]<<endl;
  67. 		vn=p[vn];
  68. 	}
  69. 	return 0;
  70. }
Success #stdin #stdout 0.04s 33224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UahJ3
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!