daily pastebin goal
20%
SHARE
TWEET

Untitled

a guest Feb 16th, 2018 481 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top