sacgajcvs

Untitled

Apr 8th, 2020
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.11 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. #define ll long long
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define endl '\n'
  16. #define mii map<ll,ll>
  17. #define msi map<string,ll>
  18. #define mis map<ll, string>
  19. #define rep(i,a,b) for(ll i=a;i<b;i++)
  20. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  21. #define trav(a, x) for(auto& a : x)
  22. #define pii pair<ll,ll>
  23. #define vi vector<ll>
  24. #define vii vector<pair<ll, ll>>
  25. #define vs vector<string>
  26. #define all(a) (a).begin(),(a).end()
  27. #define F first
  28. #define S second
  29. #define sz(x) (ll)x.size()
  30. #define hell 1000000007
  31. #define lbnd lower_bound
  32. #define ubnd upper_bound
  33. #define max(a,b) (a>b?a:b)
  34. #define min(a,b) (a<b?a:b)
  35.  
  36. /* For Debugging */
  37. #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
  38. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  39. #define what_is(x) cerr << #x << " is " << x << endl;
  40.  
  41. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  42. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  43. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  44. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  45. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  46. using namespace __gnu_pbds;
  47. using namespace std;
  48. #define PI 3.141592653589793
  49. #define N 100005
  50. vi v(N);
  51. vi a[3000005];
  52. ll n;
  53.  
  54. void call(ll& tmpk)
  55. {
  56. ll j;
  57. // rep(i,0,n)
  58. // cout<<v[i]<<" ";
  59. // cout<<endl;
  60. rep(i,1,n)
  61. {
  62. j=i;
  63. while(v[j]==0 && v[j-1]==1)
  64. {
  65. a[tmpk].pb(j-1);
  66. swap(v[j],v[j-1]);
  67. tmpk++;
  68. j--;
  69. }
  70. }
  71. }
  72.  
  73. void solve()
  74. {
  75. ll k;
  76. cin>>n>>k;
  77. string s;
  78. cin>>s;
  79. ll cnt=0,sum=0;
  80. rep(i,0,n)
  81. {
  82. v[i]=(s[i]=='L'?0:1);
  83. if(v[i])
  84. cnt++;
  85. else
  86. sum+=cnt;
  87. }
  88. // what_is(sum);
  89. if(sum<k)
  90. {
  91. cout<<-1<<endl;
  92. return;
  93. }
  94. ll tmpk=0;
  95. ll tt=0;
  96. vi tmp;
  97. while(sum>0)
  98. {
  99. tmp.clear();
  100. rep(i,1,n)
  101. {
  102. if(v[i-1] && !v[i])
  103. tmp.pb(i-1);
  104. }
  105. if(sum-sz(tmp)>=k-tmpk-1)
  106. {
  107. sum-=sz(tmp);
  108. trav(i,tmp)
  109. swap(v[i],v[i+1]);
  110. a[tmpk]=tmp;
  111. tmpk++;
  112. }
  113. else
  114. {
  115. ll j=0;
  116. // trav(lll,tmp)
  117. // cerr<<lll<<" ";
  118. // cerr<<endl;
  119. while(sum>k-tmpk-1)
  120. {
  121. swap(v[tmp[j]],v[tmp[j]+1]);
  122. a[tmpk].pb(tmp[j]);
  123. j++;
  124. sum--;
  125. }
  126. tmpk++;
  127. call(tmpk);
  128. break;
  129. }
  130. if(k-tmpk<=0 && sum>0)
  131. {
  132. cout<<-1<<endl;
  133. return;
  134. }
  135. }
  136. if(tmpk<k)
  137. call(tmpk);
  138. rep(i,0,k)
  139. {
  140. cout<<sz(a[i])<<" ";
  141. trav(j,a[i])
  142. cout<<j+1<<" ";
  143. cout<<endl;
  144. }
  145. return;
  146. }
  147. int main()
  148. {
  149. FAST
  150. #ifndef ONLINE_JUDGE
  151. // freopen ("input.txt","r",stdin);
  152. // freopen("output.txt","w",stdout);
  153. #endif
  154. int TESTS=1;
  155. // cin>>TESTS;
  156. while(TESTS--)
  157. {
  158. solve();
  159. }
  160. TIME
  161. return 0;
  162. }
Advertisement
Add Comment
Please, Sign In to add comment