fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <list>
  4. #include <algorithm>
  5. using namespace std;
  6. const int MAX=1e6;
  7. const int MAXP=(1e5)+1;
  8. char message[MAX+1], encrypted[MAX+1];
  9. int key[MAXP], both[MAX], known[MAX], nkn;
  10. list<int> tofind;
  11. bool feasible(int n){
  12. 	memset(key, -1, sizeof(int)*n);
  13. 	for(int it=0; it<nkn; it++){
  14. 		int pos=known[it];
  15. 		if(key[pos%n]==-1) key[pos%n]=both[pos];
  16. 		else if(key[pos%n]!=both[pos])return 0;
  17. 	}
  18. 	return 1;
  19. }
  20. int main(){
  21. 	int t; scanf("%d", &t);
  22. 	while(t--){
  23. 		int m; scanf("%d", &m);
  24. 		scanf("%s %s", message, encrypted);
  25. 		tofind.clear();
  26. 		nkn=0;
  27. 		int ntofind = 0;
  28. 		for(int i=0; message[i]!=0; i++)
  29. 			if(message[i]!='*'&&encrypted[i]!='*'){
  30. 					known[nkn++]=i;
  31. 					both[i]=(26+encrypted[i]-message[i])%26;
  32. 			}
  33. 			else if(message[i]=='*'&&encrypted[i]!='*')
  34. 					tofind.push_back(i), ntofind++;
  35. 		list<int>::iterator it;
  36. 		m = min(m, (int)strlen(message));
  37. 		for(int n=m/2 +1; n<=m; n++)
  38. 			if(feasible(n)){
  39. 				it=tofind.begin();
  40. 				while(it!=tofind.end())
  41. 					if(key[(*it)%n]==-1){
  42. 						message[*it]='*';
  43. 						it=tofind.erase(it);
  44. 					}
  45. 					else if(message[*it]=='*'){
  46. 						message[*it]=(encrypted[*it]-'A'+26-key[(*it)%n])%26 + 'A';
  47. 						it++;
  48. 					}
  49. 					else if(message[*it] != (encrypted[*it]-'A'+26-key[(*it)%n])%26 + 'A'){
  50. 						message[*it]='*';
  51. 						it=tofind.erase(it);
  52. 					}
  53. 					else it++;
  54. 			}
  55. 		printf("%s\n", message);
  56. 	}
  57. }
  58.  
Runtime error #stdin #stdout 0.06s 12888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/IusETD
problem CRYPTO4, based on SPOJ submission 16063884 (C++ 4.3.2), 2016-01-11 21:13:40
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!