Guest User

Untitled

a guest
Mar 7th, 2018
323
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4.  
  5. using namespace std;
  6.  
  7. const int N = 200 * 1000 + 13;
  8.  
  9. int n;
  10. int cnt[10];
  11. string s, t;
  12. int pr0[N];
  13.  
  14. bool check(int pos){
  15.     int c = accumulate(cnt, cnt + 10, 0);
  16.    
  17.     if (c > n - pos)
  18.         return false;
  19.     if (pr0[n - c] - pr0[pos] > 0)
  20.         return true;
  21.    
  22.     int nxt = 0;
  23.    
  24.     for (int i = n - c; i < n; ++i, ++nxt){
  25.         while (cnt[nxt] == 0) ++nxt;
  26.        
  27.         if (s[i] > '0' + nxt)
  28.             return true;
  29.         if (s[i] < '0' + nxt)
  30.             return false;
  31.     }
  32.    
  33.     return false;
  34. }
  35.  
  36. bool can(int pos){
  37.     int c = accumulate(cnt, cnt + 10, 0);
  38.     return (c <= n - pos);
  39. }
  40.  
  41. void fix(int pos){
  42.     int c = accumulate(cnt, cnt + 10, 0);
  43.    
  44.     t += string(n - pos - c, '9');
  45.    
  46.     int nxt = 9;
  47.     while (nxt >= 0){
  48.         while (nxt >= 0 && cnt[nxt] == 0) --nxt;
  49.         if (nxt >= 0){
  50.             t += '0' + nxt;
  51.             --nxt;
  52.         }
  53.     }
  54. }
  55.  
  56. char buf[N];
  57.  
  58. bool read(){
  59.     if (scanf("%s", buf) != 1)
  60.         return false;
  61.    
  62.     s = buf;
  63.     n = s.size();
  64.    
  65.     return true;
  66. }
  67.  
  68. void solve(){  
  69.     t = "";
  70.    
  71.     pr0[0] = 0;
  72.     forn(i, n)
  73.         pr0[i + 1] = pr0[i] + (s[i] > '0');
  74.    
  75.     if (s[0] == '1' && pr0[n] == 1){
  76.         printf("%s\n", string(n - 2, '9').c_str());
  77.         return;
  78.     }
  79.    
  80.     if (s[0] == '1' && s[n - 1] == '1' && pr0[n] == 2){
  81.         printf("%s\n", string(n - 2, '9').c_str());
  82.         return;
  83.     }
  84.    
  85.     memset(cnt, 0, sizeof(cnt));
  86.     forn(i, n){
  87.         if (i < n - 1){
  88.             cnt[s[i] - '0'] ^= 1;
  89.             if (check(i + 1)){
  90.                 t += s[i];
  91.                 continue;
  92.             }
  93.             cnt[s[i] - '0'] ^= 1;
  94.         }
  95.        
  96.         for (char c = s[i] - 1; c >= '0'; --c){
  97.             cnt[c - '0'] ^= 1;
  98.             if (can(i + 1)){
  99.                 t += c;
  100.                 fix(i + 1);
  101.                 break;
  102.             }
  103.             cnt[c - '0'] ^= 1;
  104.         }
  105.        
  106.         break;
  107.     }
  108.    
  109.     printf("%s\n", t.c_str());
  110. }
  111.  
  112. int main(){
  113.     int tc;
  114.     scanf("%d", &tc);
  115.     while (tc--){
  116.         read();
  117.         solve();
  118.     }
  119.     return 0;
  120. }
RAW Paste Data