SHARE
TWEET

Untitled

a guest Jul 16th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define PB push_back
  6. #define MP make_pair
  7. #define REP(i,a,b) for (int i = a; i <= b; i++)
  8. #define debug(i) cout << i << endl;
  9. #define debugarr(a) for(auto i : a) cout << i << " ";
  10.  
  11. #define ll long long
  12. #define vi vector<int>
  13. #define vll vector<ll>
  14. #define pi pair<int,int>
  15. #define pll pair<ll, ll>
  16. #define vpi vector<pi>
  17.  
  18. #define N 100010
  19. #define LEFT(x) (x<<1)
  20. #define RIGHT(x) ((x<<1)|1)
  21.  
  22. using namespace std;
  23.  
  24. int arr[N];
  25. pi tree[N * 4];
  26.  
  27. pi query(int i, int l, int r, int x, int y) {
  28.     if(l >= x && r <= y) return tree[i];
  29.     else if(r < x || l > y) return MP(-1,-1);
  30.     else {
  31.         int mid = (l+r)>>1;
  32.         pi res = MP(-1, -1);
  33.         if(x <= mid)
  34.             res = query(LEFT(i), l, mid, x, y);
  35.         if(y > mid) {
  36.             pi q = query(RIGHT(i), mid+1, r, x, y);
  37.             if(q.F > res.F)
  38.                 res = q;
  39.             else if(q.F == res.F && q.S < res.S)
  40.                 res = q;
  41.         }
  42.         return res;
  43.     }
  44. }
  45.  
  46. void build(int i, int l, int r) {
  47.     if(l == r) tree[i] = MP(arr[l], l);
  48.     else {
  49.         int mid = (l+r)>>1;
  50.         build(LEFT(i), l, mid);
  51.         build(RIGHT(i), mid+1, r);
  52.        
  53.         if(tree[LEFT(i)].F > tree[RIGHT(i)].F)
  54.             tree[i] = tree[LEFT(i)];
  55.         else if(tree[LEFT(i)].F < tree[RIGHT(i)].F)
  56.             tree[i] = tree[RIGHT(i)];
  57.         else {
  58.             if(tree[LEFT(i)].S < tree[RIGHT(i)].S)
  59.                 tree[i] = tree[LEFT(i)];
  60.             else
  61.                 tree[i] = tree[RIGHT(i)];
  62.         }
  63.     }
  64. }
  65.  
  66. int main() {
  67.     ios_base::sync_with_stdio(false);
  68.  
  69.     int n, d;
  70.     while(cin >> n >> d && n != 0) {
  71.         memset(tree, 0, sizeof tree);
  72.         int need = n - d;
  73.         for(int i = 1; i <= n; i++) {
  74.             char k;
  75.             cin >> k;
  76.             arr[i] = k - '0';
  77.         }
  78.         build(1, 1, n);
  79.        
  80.         int last_choose = -1;
  81.         string ans = "";
  82.         while(need--) {
  83.             pi next = query(1, 1, n, last_choose+1, n - need);
  84.             last_choose = next.S;
  85.             ans += (char) next.F + '0';
  86.         }
  87.         cout << ans << endl;
  88.     }
  89. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top