fork download
copy 
  1. //http://w...content-available-to-author-only...f.com/COOK52/problems/PETERSEN
  2. // Peterson
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <algorithm>
  7. #include <map>
  8. #include <queue>
  9. #include <string>
  10. #include <string.h>
  11.  
  12. #define PI pair<int,int>
  13. #define MP(a,b) make_pair(a,b)
  14.  
  15. #define MOD 1000000007
  16. #define long long ll
  17.  
  18. using namespace std;
  19.  
  20. int main()
  21. {
  22. 	int t;
  23. 	cin >> t;
  24. 	while(t--)
  25. 	{
  26. 		string s;
  27. 		cin >> s;
  28. 		if ( s[0] == '#' ) {
  29. 			cout<<s<<'\n';
  30. 			++t;
  31. 			continue;
  32. 		}
  33. 		int n = s.length();
  34. 		int a[n+1];
  35. 		for(int i=0; i<n; i++) a[i+1] = s[i] - 'A';
  36. 		int dp1[n+1], dp2[n+1];		// store prev (1-outer, 2-inner)
  37.  
  38. 		dp1[1] = 1;
  39. 		dp2[1] = 1;
  40. 		for(int i=2; i<=n; i++){ dp1[i] = -1; dp2[i] = -1; }
  41. 		for(int i=2; i<=n; i++)
  42. 		{
  43. 			if(a[i] == a[i-1])
  44. 			{
  45. 				if(dp2[i-1] != -1) dp1[i] = 2;		// outer to inner
  46. 				else dp1[i] = -1;
  47. 				if(dp1[i-1] != -1) dp2[i] = 1;		// inner to outer
  48. 				else dp2[i] = -1;
  49. 			}
  50. 			else
  51. 			{
  52. 				// adj
  53. 				if(a[i] == (a[i-1]+1)%5 || a[i-1] == (a[i]+1)%5)
  54. 				{
  55. 					if(dp1[i-1] != -1) dp1[i] = 1;
  56. 				}
  57. 				else dp1[i] = -1;
  58. 				if(a[i] == (a[i-1]+2)%5 || a[i-1] == (a[i]+2)%5)
  59. 				{
  60. 					if(dp2[i-1] != -1) dp2[i] = 2;
  61. 				}
  62. 				else dp2[i] = -1;
  63. 			}
  64. 		}
  65.  
  66. 		if(dp1[n]==-1 && dp2[n]==-1)
  67. 		{
  68. 			cout << -1 << endl;
  69. 			return 0;
  70. 		}
  71. 		//~ for(int i=1; i<=n; i++) cout << dp1[i] << " "; cout << endl;
  72. 		//~ for(int i=1; i<=n; i++) cout << dp2[i] << " "; cout << endl;
  73.  
  74. 		vector<int> p1;
  75. 		vector<int> p2;
  76. 		int nn = 1;
  77. 		for(int i=n; i>=1; i--)
  78. 		{
  79. 			if(nn==1 && dp1[i] != -1)
  80. 			{
  81. 				p1.push_back(a[i]);		// outer node
  82. 				nn = dp1[i];
  83. 			}
  84. 			else if(nn==2 && dp2[i] != -1)
  85. 			{
  86. 				p1.push_back(a[i]+5);	// inner node
  87. 				nn = dp2[i];
  88. 			}
  89. 		}
  90.  
  91. 		nn = 2;
  92. 		for(int i=n; i>=1; i--)
  93. 		{
  94. 			if(nn==1 && dp1[i] != -1)
  95. 			{
  96. 				p2.push_back(a[i]);		// outer node
  97. 				nn = dp1[i];
  98. 			}
  99. 			else if(nn==2 && dp2[i] != -1)
  100. 			{
  101. 				p2.push_back(a[i]+5);	// inner node
  102. 				nn = dp2[i];
  103. 			}
  104. 		}
  105.  
  106. 		reverse(p1.begin(), p1.end());
  107. 		reverse(p2.begin(), p2.end());
  108. 		int s1 = p1.size();
  109. 		int s2 = p2.size();
  110. 		if(s2 < s1 || s2==s1 && p1[0] < p2[0])
  111. 		{
  112. 			if(s1==n) for(int i=0; i<s1; i++) cout << p1[i];
  113. 			else cout << -1;
  114. 		}
  115. 		else if(s1 < s2 || s1==s2 && p2[0] < p1[0])
  116. 		{
  117. 			if(s2==n) for(int i=0; i<s2; i++) cout << p2[i];
  118. 			else cout << -1;
  119. 		}
  120. 		cout << endl;
  121. 	}
  122. 	return 0;
  123. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
2
AABD
AABE
stdout
copy 
-1
https://ideone.com/p3WaH5
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!