Guest User

Untitled

a guest
Feb 16th, 2018
730
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 5043;
  6. const int M = 12;
  7.  
  8. bool dp[N][(1 << M)];
  9.  
  10. typedef pair<int, int> pt;
  11.  
  12. #define x first
  13. #define y second
  14.  
  15. vector<int> bits[(1 << M)];
  16.  
  17. int main()
  18. {
  19. string s;
  20. cin >> s;
  21. int n = s.size();
  22. string ans;
  23. dp[0][0] = 1;
  24. vector<pt> cur;
  25. cur.push_back(make_pair(0, 0));
  26. int final_sz = n;
  27. int cur_len = 1;
  28. int cnt = 0;
  29. while((1 << cnt) < n)
  30. cnt++;
  31. cnt--;
  32.  
  33. for(int i = 0; i < (1 << cnt); i++)
  34. for(int j = 0; j < cnt; j++)
  35. if ((i & (1 << j)) == 0)
  36. bits[i].push_back(j);
  37. while(final_sz > cur_len)
  38. {
  39. final_sz -= cur_len;
  40. cur_len *= 2;
  41. }
  42. while(ans.size() < final_sz)
  43. {
  44. char min_chr = 'z';
  45. for(int i = 0; i < cur.size(); i++)
  46. {
  47. auto x = cur[i];
  48. for(auto y : bits[x.y])
  49. {
  50. if (dp[x.x + (1 << y)][x.y ^ (1 << y)] == 0)
  51. {
  52. cur.push_back(make_pair(x.x + (1 << y), x.y ^ (1 << y)));
  53. dp[x.x + (1 << y)][x.y ^ (1 << y)] = 1;
  54. }
  55. }
  56. min_chr = min(min_chr, s[x.x]);
  57. }
  58. vector<pt> new_cur;
  59. ans.push_back(min_chr);
  60. for(auto x : cur)
  61. if (s[x.x] == min_chr)
  62. {
  63. dp[x.x + 1][x.y] = 1;
  64. new_cur.push_back(make_pair(x.x + 1, x.y));
  65. }
  66. cur = new_cur;
  67. }
  68. cout << ans << endl;
  69. }
RAW Paste Data