Advertisement
Saleh127

UVa live 6948

Oct 27th, 2020
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. vector<ll>ans;
  7. bool vis[1000];
  8. string x;
  9. ll len;
  10.  
  11. void backtrack(ll ind)
  12. {
  13.  
  14. if(ind>=x.size()) return;
  15.  
  16. ll cur=x[ind]-'0';
  17.  
  18. if(cur!=0 && vis[cur]==0)
  19. {
  20. vis[cur]=1;
  21.  
  22. ans.push_back(cur);
  23.  
  24. backtrack(ind+1);
  25.  
  26. if(ans.size()==len) return;
  27.  
  28. ans.pop_back();
  29.  
  30. vis[cur]=0;
  31. }
  32.  
  33. if((ind+1) >=x.size()) return;
  34.  
  35. cur=cur*10+ (x[ind+1]-'0');
  36.  
  37. if(cur!=0 && cur<=len && vis[cur]==0)
  38. {
  39. vis[cur]=1;
  40.  
  41. ans.push_back(cur);
  42.  
  43. backtrack(ind+2);
  44.  
  45. if(ans.size()==len) return;
  46.  
  47. ans.pop_back();
  48.  
  49. vis[cur]=0;
  50. }
  51. }
  52.  
  53. int main()
  54. {
  55. ios_base::sync_with_stdio(0);
  56. cin.tie(0);
  57. cout.tie(0);
  58.  
  59. ///freopen("joke.in", "r", stdin);
  60. ///freopen("joke.out", "w", stdout);
  61.  
  62. ll i;
  63.  
  64. cin>>x;
  65.  
  66. if( x.size()<10)
  67. {
  68. len= x.size();
  69. }
  70. else
  71. {
  72. len=9+(x.size()-9)/2;
  73. }
  74. memset(vis,0,sizeof(vis));
  75.  
  76. backtrack(0);
  77.  
  78. for(i=0; i<ans.size(); i++)
  79. {
  80. if(i==0) cout<<ans[i];
  81. else cout<<" "<<ans[i];
  82. }
  83. cout<<endl;
  84.  
  85. return 0;
  86. }
  87.  
Advertisement
RAW Paste Data Copied
Advertisement