fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long* SieveOfEratosthenes(int n) 
  4. { 
  5.     // Create a boolean array "prime[0..n]" and initialize 
  6.     // all entries it as true. A value in prime[i] will 
  7.     // finally be false if i is Not a prime, else true. 
  8.     bool prime[n+1]; 
  9.     memset(prime, true, sizeof(prime)); 
  10.     long *arr=new long[78499];
  11.     for (int p=2; p*p<=n; p++) 
  12.     { 
  13.         // If prime[p] is not changed, then it is a prime 
  14.         if (prime[p] == true) 
  15.         { 
  16.             // Update all multiples of p greater than or  
  17.             // equal to the square of it 
  18.             // numbers which are multiple of p and are 
  19.             // less than p^2 are already been marked.  
  20.             for (int i=p*p; i<=n; i += p) 
  21.                 prime[i] = false; 
  22.         } 
  23.     } 
  24.   int flag=0;
  25.     // Print all prime numbers 
  26.     for (int p=2; p<=n; p++) 
  27.        if (prime[p]){ 
  28.           // cout << p << " "; 
  29.             arr[flag++]=p;
  30.     }
  31.         // cout<<flag<<endl;
  32.         return arr;
  33. } 
  34.  
  35. int main(){
  36. 	int t=0;
  37. 	cin>>t;
  38. 	int cse=0;
  39. 	long *arr=SieveOfEratosthenes(100000);
  40. 	while(t--){
  41. 		cse+=1;
  42.  
  43. 		set<long> str;
  44. 		int n=0;
  45. 		int m=0;
  46. 		cin>>m>>n;
  47. 		long num[n];
  48. 		long low[1][2];
  49. 		low[0][0]=1000000;
  50. 		int flag=0;
  51. 		for (int i = 0; i < n; ++i)
  52. 		{
  53. 			long temp=0;
  54. 			cin>>temp;
  55. 			num[i]=temp;
  56. 			if(temp<low[0][0]){
  57. 				low[0][0]=temp;
  58. 				low[0][1]=i;
  59. 				flag=i;
  60. 			}
  61.  
  62. 		}
  63.  
  64. 		long pair[1][2];
  65. 		for (int i = 0; i < 78499; ++i)
  66. 		{
  67. 			if(fmod(low[0][0],arr[i])==0){
  68. 				pair[0][0]=arr[i];
  69. 				pair[0][1]=low[0][0]/arr[i];
  70. 				break;
  71. 			}
  72. 		}
  73. 		//pair contains the decoded value at i
  74. 		//pair may lie anywhere b/n the array so decode it both the ways
  75. 		//to find the list of prime numbers
  76. 		// cout<<"Decoded value at :"<<flag+1<<" "<<pair[0][0]<<" "<<pair[0][1]<<endl;
  77. //now create an array of 32 numbers
  78. 		long res[n+1];
  79. 		//curing the left sub array
  80. 		long left=pair[0][0];
  81. 		long right=pair[0][1];
  82. 		if(fmod(num[flag+1],pair[0][0])==0){
  83. 			long t=left;
  84. 			left=right;
  85. 			right=t;
  86. 		}
  87. 		res[flag+1]=right;
  88. 		res[flag]=left;
  89. 		// cout<<"\nFlags are: "<<left<<" "<<right<<endl;
  90. 		// cout<<"Curing right of "<<flag<<endl;
  91. 		for (int i = flag+1; i < n; ++i)
  92. 		{
  93. 			right=num[i]/right;
  94. 			res[i+1]=right;
  95. 			// cout<<res[i]<<endl;
  96. 		}
  97. 		// cout<<"\nCuring left of "<<flag<<endl;
  98. 		for (int i = flag-1; i >-1; i--)
  99. 		{
  100. 			left=num[i]/left;
  101. 			res[i]=left;
  102. 			// cout<<res[i]<<endl;
  103.  
  104. 		}
  105.  
  106.  
  107. 		// sort(res,res+n+1);
  108. 		set<long> res2;
  109. 		// cout<<"\nCured Array is:\n";
  110. 		for (int i = 0; i < n+1; ++i)
  111. 		{
  112. 			// cout<<res[i]<<endl;
  113. 			res2.insert(res[i]);
  114. 		}
  115. 		// cout<<"\nSorted Array is:\n";
  116. 		set<long>::iterator itr;
  117. 		map<long,char> mp;
  118. 		int ch=65;
  119. 		for (itr = res2.begin(); itr!=res2.end();itr++)
  120. 		{
  121. 			mp.insert(make_pair(*itr,(char)ch++));
  122. 		}
  123. 		cout<<"Case #"<<cse<<": ";
  124. 		for (int i = 0; i < n+1; ++i)
  125. 		{
  126. 			auto it=mp.find(res[i]);
  127. 			cout<<(*it).second;
  128. 		}
  129.  
  130. 		cout<<endl;
  131.  
  132.  
  133.  
  134. 		}
  135.  
  136. 	return  0;
  137. }
Success #stdin #stdout 0s 15856KB
comments (?)
stdin
copy 
2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543
stdout
copy 
Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ
https://ideone.com/mbBiTy
language:
C++14 (gcc 8.3)
created:
6 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!