fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. char s[5001];
  6. char s1[5001],s2[5001];
  7.  
  8. int main(int argc, char **argv)
  9. {
  10. 	int T,N,i,j,smallestindex,shiftfrom,smallest,greatestindex,greatest;
  11.  
  12. 	for(scanf("%d",&T);T>0;T--)
  13. 	{
  14. 		scanf("%d",&N);
  15. 		scanf("%s",s);
  16.  
  17. 		shiftfrom=N;
  18. 		for(i=0;i<N;i++)
  19. 		{
  20. 			smallest=s[i];
  21. 			smallestindex=i;
  22. 			for(j=i+1;j<N;j++)
  23. 			{
  24. 				if(s[j]<=smallest)
  25. 				{
  26. 					smallest=s[j];
  27. 					smallestindex=j;
  28. 				}
  29. 			}
  30. 			if(smallest!=s[i])
  31. 			{
  32. 				shiftfrom=i;
  33. 				break;
  34. 			}
  35. 		}
  36.  
  37. 		if(shiftfrom==N)
  38. 		{
  39. 			for(i=0;i<N;i++)
  40. 			{
  41. 				s1[i]=s[i];
  42. 			}
  43. 		}
  44. 		else
  45. 		{
  46. 			for(i=0;i<shiftfrom;i++)
  47. 			{
  48. 				s1[i]=s[i];
  49. 			}
  50. 			s1[shiftfrom]=s[smallestindex];
  51. 			for(i=shiftfrom;i<N;i++)
  52. 			{
  53. 				if(i<smallestindex)
  54. 				{
  55. 					s1[i+1]=s[i];
  56. 				}
  57. 				else if(i>smallestindex)
  58. 				{
  59. 					s1[i]=s[i];
  60. 				}
  61. 			}
  62. 		}
  63. 		s1[N]='\0';
  64.  
  65.  
  66. 		shiftfrom=-1;
  67. 		for(i=N-1;i>=0;i--)
  68. 		{
  69. 			greatest=s[i];
  70. 			greatestindex=i;
  71. 			for(j=i-1;j>=0;j--)
  72. 			{
  73. 				if(s[j]>=greatest)
  74. 				{
  75. 					greatest=s[j];
  76. 					greatestindex=j;
  77. 				}
  78. 			}
  79. 			if(greatest!=s[i])
  80. 			{
  81. 				shiftfrom=i;
  82. 				break;
  83. 			}
  84. 		}
  85.  
  86. 		if(shiftfrom==-1)
  87. 		{
  88. 			for(i=0;i<N;i++)
  89. 			{
  90. 				s2[i]=s[i];
  91. 			}
  92. 		}
  93. 		else
  94. 		{
  95. 			for(i=N-1;i>shiftfrom;i--)
  96. 			{
  97. 				s2[i]=s[i];
  98. 			}
  99. 			s2[shiftfrom]=s[greatestindex];
  100. 			for(i=shiftfrom;i>=0;i--)
  101. 			{
  102. 				if(i>greatestindex)
  103. 				{
  104. 					s2[i-1]=s[i];
  105. 				}
  106. 				else if(i<greatestindex)
  107. 				{
  108. 					s2[i]=s[i];
  109. 				}
  110. 			}
  111. 		}
  112. 		s2[N]='\0';
  113.  
  114. 		if(strcmp(s1,s2)<=0)
  115. 		{
  116. 			for(i=0;i<N;i++)
  117. 			{
  118. 				printf("%c",s1[i]);
  119. 			}
  120. 		}
  121. 		else
  122. 		{
  123. 			for(i=0;i<N;i++)
  124. 			{
  125. 				printf("%c",s2[i]);
  126. 			}
  127. 		}
  128. 		printf("\n");
  129. 	}
  130.  
  131. 	return 0;
  132. }
Success #stdin #stdout 0s 3156KB
comments (?)
stdin
copy 
1
4
ABAA
stdout
copy 
AAAB
https://ideone.com/rU6isc
language:
C++ (gcc 8.3)
created:
9 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!