Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. #include <unordered_set>
  8. #include <map>
  9. #include <unordered_map>
  10. #include <random>
  11. #include <chrono>
  12. #include <string>
  13. #include <bitset>
  14. #include <cassert>
  15. #include <queue>
  16. #include <memory>
  17.  
  18. //#pragma comment(linker, "/STACK:16777216")
  19. //#pragma GCC optimize("O3")
  20. //#pragma GCC optimize("Ofast")
  21. //#pragma GCC optimize("unroll-loops")
  22. //#pragma GCC optimize("unswitch-loops")
  23. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt,tune=native")
  24.  
  25. using namespace std;
  26.  
  27. //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  28.  
  29. #define ll long long
  30. #define ull unsigned long long
  31. //#define double long double
  32. //#define int ll
  33. //#define int ull
  34. //#define int short
  35. //#define int unsigned short
  36. //#define int unsigned int
  37. #define mp make_pair
  38. #define F first
  39. #define S second
  40. #define pii pair<int, int>
  41. #define hash hash228
  42. const int SZ = 2e5 + 4;
  43. const double EPS = 1e-7;
  44. const int mod = 998244353;
  45. const int hashpow = 127;
  46. const int inf = 2e9;
  47.  
  48. struct custom_hash {
  49.     static uint64_t splitmix64(uint64_t x) {
  50.         // http://xorshift.di.unimi.it/splitmix64.c
  51.         x += 0x9e3779b97f4a7c15;
  52.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  53.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  54.         return x ^ (x >> 31);
  55.     }
  56.  
  57.     size_t operator()(uint64_t x) const {
  58.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  59.         return splitmix64(x + FIXED_RANDOM);
  60.     }
  61. };
  62.  
  63. int n, k;
  64. string s;
  65.  
  66. void read() {
  67.     cin >> n >> k >> s;
  68. }
  69.  
  70. void solve() {
  71.     vector<set<int>> ans;
  72.     int sum = 0;
  73.     while (true) {
  74.         set<int> tmp;
  75.         for (int j = 0; j < n - 1; ++j) {
  76.             if (s[j] == 'R' && s[j + 1] == 'L') {
  77.                 swap(s[j], s[j + 1]);
  78.                 tmp.insert(j);
  79.                 ++sum;
  80.                 ++j;
  81.             }
  82.         }
  83.         if (tmp.empty()) break;
  84.         ans.push_back(tmp);
  85.     }
  86.  
  87.     if (sum < k || k < ans.size()) {
  88.         cout << -1;
  89.         return;
  90.     }
  91.  
  92.     int tmp = 0;
  93.     bool z = true;
  94.     for (auto &u : ans) {
  95.         if (z) {
  96.             if (tmp + 1 + sum - u.size() >= k) {
  97.                 cout << u.size() << " ";
  98.                 for (auto v : u) {
  99.                     cout << v + 1 << " ";
  100.                 }
  101.                 cout << "\n";
  102.                 sum -= u.size();
  103.                 ++tmp;
  104.             } else {
  105.                 int x = tmp + 1 + sum - k;
  106.  
  107.                 int j = 0;
  108.                 if (x) {
  109.                     cout << x << " ";
  110.                     for (auto v : u) {
  111.                         cout << v + 1 << " ";
  112.                         ++j;
  113.                         if (j == x) break;
  114.                     }
  115.                     cout << "\n";
  116.                 }
  117.  
  118.                 int q = 0;
  119.                 for (auto v : u) {
  120.                     if (q >= j) {
  121.                         cout << 1 << " " << v + 1 << "\n";
  122.                     }
  123.                     ++q;
  124.                 }
  125.                 z = false;
  126.             }
  127.         } else {
  128.             for (auto v : u) {
  129.                 cout << 1 << " " << v + 1 << "\n";
  130.             }
  131.         }
  132.     }
  133. }
  134.  
  135. signed main() {
  136.  
  137. #ifdef __LOCAL
  138.     freopen("input.txt", "r", stdin);
  139.     freopen("output.txt", "w", stdout);
  140. #else
  141.     ios_base::sync_with_stdio(0);
  142.     cin.tie(0);
  143. #endif
  144.  
  145. //    int t;
  146. //    cin >> t;
  147. //    for (int i = 0; i < t; ++i) {
  148.         read();
  149.         solve();
  150. //    }
  151.  
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement