fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. string makeLargestPalindrome(string num, int d, int k) {
  7.     vector<bool> changed(d, false);
  8.     int left = 0, right = d - 1;
  9.     int minChanges = 0;
  10.  
  11.     // First pass: Make it a palindrome
  12.     while (left < right) {
  13.         if (num[left] != num[right]) {
  14.             char maxChar = max(num[left], num[right]);
  15.             num[left] = num[right] = maxChar;
  16.             changed[left] = changed[right] = true;
  17.             minChanges++;
  18.         }
  19.         left++;
  20.         right--;
  21.     }
  22.  
  23.     if (minChanges > k)
  24.         return "-1"; // Not possible to make palindrome within k changes
  25.  
  26.     int remainingChanges = k - minChanges;
  27.     left = 0;
  28.     right = d - 1;
  29.  
  30.     // Second pass: Maximize palindrome value by changing to '9'
  31.     while (left <= right) {
  32.         if (left == right) {
  33.             if (remainingChanges > 0 && num[left] != '9') {
  34.                 num[left] = '9';
  35.                 remainingChanges--;
  36.             }
  37.         } else {
  38.             if (num[left] != '9') {
  39.                 if (changed[left] || changed[right]) {
  40.                     if (remainingChanges >= 1) {
  41.                         num[left] = num[right] = '9';
  42.                         remainingChanges--;
  43.                     }
  44.                 } else {
  45.                     if (remainingChanges >= 2) {
  46.                         num[left] = num[right] = '9';
  47.                         remainingChanges -= 2;
  48.                     }
  49.                 }
  50.             }
  51.         }
  52.         left++;
  53.         right--;
  54.     }
  55.  
  56.     return num;
  57. }
  58.  
  59. int main() {
  60.     int t;
  61.     cin >> t;
  62.     while (t--) {
  63.         int d, k;
  64.         cin >> d >> k;
  65.         string number;
  66.         cin >> number;
  67.  
  68.         string result = makeLargestPalindrome(number, d, k);
  69.         cout << result << endl;
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
1
6 2
609046
stdout
copy 
649946
https://ideone.com/O2SoT0
language:
C++ (gcc 8.3)
created:
1 day 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!