fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14. typedef pair<int,int> pii;
  15. const ll Mod = 1e9+7;
  16. const ll Maxn = 1e6+69;
  17. const ll Maxm = 1e3;
  18. const ll oo = 1e18;
  19. const int inf = 1e9;
  20.  
  21. string s;
  22. int Minid[10];
  23. pii dp[Maxn];
  24. // Minid[x]: Lưu trữ chỉ số của số t/m đề bài, với điều kiện thằng bắt đầu bằng giá trị x
  25.  
  26. pii FindMin (int End)
  27. {
  28.     int resleng = inf, nextid;
  29.     for (int i = 9 ; i >= End ; --i )
  30.     {
  31.         if(resleng>=dp[Minid[i]].fi)
  32.         {
  33.             resleng = dp[Minid[i]].fi;
  34.             nextid = Minid[i];
  35.         }
  36.     }
  37.     return {resleng,nextid};
  38. }
  39.  
  40. void Print()
  41. {
  42.     pii res = FindMin(1);
  43.     int x = res.se;
  44.     while(x<s.size())
  45.     {
  46.         cout << s[x];
  47.         x = dp[x].se;
  48.     }
  49. }
  50.  
  51. bool Check ()
  52. {
  53.     int check[10] = {0};
  54.     for (auto x:s) check[x-'0']=1;
  55.     for (int i = 1 ; i <= 9 ; ++i)
  56.         if(!check[i])
  57.     {
  58.         cout << char(i+'0');
  59.         return false;
  60.     }
  61.     return true;
  62. }
  63.  
  64. void Do()
  65. {
  66.     cin >> s ;
  67.     int n = s.size()-1;
  68.     if(!Check()) return;
  69.     for (int i = 0 ; i <= 9 ; ++i)
  70.     {
  71.         s.pb(char(i+'0'));
  72.         Minid[i] = s.size()-1;
  73.         dp[s.size()-1] = {0,inf};
  74.     }
  75.     for (int i = n ; i >= 0 ; i--)
  76.     {
  77.         pii MinLeng = FindMin(0);
  78.         dp[i] = {1 + MinLeng.fi,MinLeng.se};
  79.         Minid[s[i]-'0']=i;
  80.     }
  81.     if(dp[0].fi==1) cout << s[dp[0].se];
  82.     else Print();
  83. }
  84.  
  85. signed main ()
  86. {
  87.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  88. #define task "test"
  89.     if(fopen(task".inp", "r")){
  90.         freopen(task".inp", "r", stdin);
  91.         freopen(task".out", "w", stdout);
  92.     }
  93.     int ntest=1;
  94.     while(ntest--) Do();
  95.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  96. }
  97.  
  98.  
Success #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time elapsed: 4ms
https://ideone.com/3UkTEI
language:
C++14 (gcc 8.3)
created:
2 days 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!