fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. int dist(char a, char b)
  25. {
  26. 	if(a>b) swap(a, b);
  27. 	int d = b - a;
  28. 	d = min(d, 26 - d);
  29. 	return d;
  30. }
  31.  
  32. const int N = 100001;
  33. int dp[N][26];
  34. int mini[N];
  35. char pos[N];
  36.  
  37. int main()
  38. {
  39. 	ios_base::sync_with_stdio(0); cin.tie(0);
  40. 	int t; cin>>t;
  41. 	while(t--)
  42. 	{
  43. 		int k; cin >> k;
  44. 		ll kk = k;
  45. 		string s; cin >> s;
  46. 		string t = s;
  47. 		int n = int(s.length());
  48. 		for(int i = 0; i < n; i++)
  49. 		{
  50. 			mini[i] = 1000000000;
  51. 			for(int j = 0; j < 26; j++)
  52. 			{
  53. 				if(i != n - 1 - i) dp[i][j] = dist(s[i], char(j+'a')) + dist(s[n-1-i], char(j+'a'));
  54. 				else dp[i][j] = dist(s[i], char(j+'a'));
  55. 				if(mini[i] > dp[i][j])
  56. 				{
  57. 					mini[i] = dp[i][j];
  58. 					pos[i] = char(j+'a');
  59. 				}
  60. 			}
  61. 			s[i] = pos[i]; s[n-1-i] = pos[i];
  62. 			k -= mini[i];
  63. 		}
  64. 		if(k < 0)
  65. 		{
  66. 			cout << -1 << '\n';
  67. 			continue;
  68. 		}
  69. 		for(int i = 0; i <= n - 1 - i; i++)
  70. 		{
  71. 			if(k < 0) break;
  72. 			for(int j = 0; j < s[i] - 'a'; j++)
  73. 			{
  74. 				if(dp[i][j] - mini[i] <= k)
  75. 				{
  76. 					k -= (dp[i][j] - mini[i]);
  77. 					s[i] = s[n-1-i] = char(j+'a'); 
  78. 					break;
  79. 				}
  80. 			}
  81. 		}
  82. 		for(int i = 0; i < n; i++)
  83. 		{
  84. 			assert(s[i]==s[n-1-i]);
  85. 		}
  86. 		ll d = 0;
  87. 		for(int i = 0; i < n; i++)
  88. 		{
  89. 			d += dist(s[i], t[i]);
  90. 		}
  91. 		assert(d<=kk);
  92. 		cout << s << '\n';
  93. 	}
  94. }
  95.  
Runtime error #stdin #stdout 0s 14112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/mNp8uk
language:
C++14 (gcc 8.3)
created:
7 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!