solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    string nearestPalindromic(string s) {
        auto get_val = [&](string &s) -> long long {
            long long n = 0;
            for (int i = 0; i < s.size(); i++) {
                n = n * 10 + s[i] - '0';
            }
            return n;
        };
        long long sval = get_val(s);
        int sz = s.size();
        typedef pair<string, string> pss;

        
        auto not_change = [&](string &s, int idx) -> pss {
            if (s == "0") return {"0", "0"};
            string res = s.substr(0, idx + 1);
            string res2 = res;
            reverse(res2.begin(), res2.end());
            string ans1 = res + res2;
            res.pop_back();
            string ans2 = res + res2;
            return {ans1, ans2};
        };

        auto add_one = [&](string &s) {
            int now = s.size() - 1;
            while (now >= 0 && s[now] == '9') now--;
            if (now == -1) {
                string ans = "1";
                for (int i = 0; i < s.size(); i++) ans += '0';
                return ans;
            } else {
                string ans = s.substr(0, now);
                ans += (s[now] + 1);
                for (int i = now + 1; i < s.size(); i++) {
                    ans += '0';
                }
                return ans;
            }
        };

        auto delete_one = [&](string &s) -> string {
            if (s == "1") return "0";
            int now = s.size() - 1;
            while (now >= 0 && s[now] == '0') now--;
            if (now == 0 && s[now] == '1') {
                string ans = "";
                for (int i = 1; i < s.size(); i++) {
                    ans += '9';
                }
                return ans;
            } else {
                string ans = s.substr(0, now);
                ans += (s[now] - 1);
                for (int i = now + 1; i < s.size(); i++) {
                    ans += '9';
                }
                return ans;
            }
        };


        auto add = [&](string &s, int idx) -> pss {
            string res = s.substr(0, idx + 1);
            res = add_one(res);
            return not_change(res, res.size());
        };

        auto del = [&](string &s, int idx) -> pss {
            string res = s.substr(0, idx + 1);
            res = delete_one(res);
            return not_change(res, res.size());
        };

        long long ans = numeric_limits<long long>::max() / 2;
        string sans;
        auto work = [&](string &s1) {
            if (s == s1) return;
            if (s1.size() > sz + 1) return;
            if (s1.size() > 19) return;
            if (s1.size() == 19 && s1[0] != '1') return;
            long long tmp = get_val(s1);
            if (abs(ans - sval) > abs(tmp - sval) || abs(ans - sval) == abs(tmp - sval) && tmp < ans) {
                ans = tmp;
                sans = s1;
            }
        };

        for (int i = 0; i < sz; i++) {
            pss s2 = not_change(s, i);
            debug(i, s2);
            work(s2.first);
            work(s2.second);
            
            s2 = add(s, i);
            debug(i, s2);
            work(s2.first);
            work(s2.second);

            s2 = del(s, i);
            debug(i, s2);
            work(s2.first);
            work(s2.second);
        }

        string ni = "";
        for (int i = 0; i < sz; i++) {
            ni += '9';
        }
        work(ni);
        ni.pop_back();
        work(ni);
        ni = "1";
        for (int i = 0; i < sz - 2; i++) {
            ni += '0';
        }
        ni += '1';
        work(ni);
        ni.pop_back();
        ni += '0';
        ni += '1';
        work(ni);


        return sans;
    }
};