Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <fstream>
  10. using namespace std;
  11.  
  12. int searchLeft(string s, int k) {
  13.     do {
  14.         --k;
  15.     } while (k >= 0 && s[k] == 'V');
  16.     return k+1;
  17. }
  18.  
  19. int searchRight(string s, int k) {
  20.     do {
  21.         ++k;
  22.     } while (k < s.size() && s[k] == 'V');
  23.     return k-1;
  24. }
  25.  
  26. int main() {
  27.     int n;
  28.     string s;
  29.     cin >> n >> s;
  30.     vector<int> steps(n, 0);
  31.     int prev = 0;
  32.     int step_cnt = 0, d = 0;
  33.     do {
  34.         d = 0;
  35.         for (int i = 0; i < n; ++i) {
  36.             if (s[i] != 'K')
  37.                 continue;
  38.        
  39.             int l = searchLeft(s, i),
  40.                 r = searchRight(s, i);
  41.  
  42.             if (i - l <= r - i) {
  43.                 // move left
  44.                 steps[i] = l-i + steps[prev];
  45.                 prev = i;
  46.             } else {
  47.                 // move right
  48.                 if (s[r] == 'K')
  49.                     continue;
  50.                 steps[i] = r - l;
  51.                 prev = 0;
  52.             }
  53.         }
  54.  
  55.         for (int i = 0; i < n; ++i) {
  56.             if (steps[i] != 0) {
  57.                 d = d + abs(steps[i]);
  58.  
  59.                 char c = s[i];
  60.                 s[i] = s[i + steps[i]];
  61.                 s[i + steps[i]] = c;
  62.             }
  63.         }
  64.         step_cnt = step_cnt + d;
  65.         cout << s << endl;
  66.     } while (d > 0);
  67.  
  68.     cout << s << endl;
  69.     cout << step_cnt << endl;
  70.  
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement