fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define MOD 1000000007 
  5. ll i,j,k,l,n,m,arr[1000005],vis[1000005];
  6. struct node
  7. {
  8. 	int ch;
  9. 	int pos;
  10. }seg[10000005],seg1[10000005];
  11. void init(int st,int end,int p)
  12. {
  13. 	int mid;
  14. 	if(st==end)
  15. 	{
  16. 		seg[p].ch=INT_MAX;
  17. 		seg[p].pos=-1;
  18. 	}
  19. 	else
  20. 	{
  21. 		mid=st+(end-st)/2;
  22. 		init(st,mid,2*p);
  23. 		init(mid+1,end,2*p+1);
  24. 		seg[p].ch=INT_MAX;
  25. 		seg[p].pos=-1;
  26. 	}
  27. }
  28. pair<int,int> query(int beg,int end,int i,int j,int p)
  29. {
  30. 	int mid;
  31. 	pair<int,int>l1;
  32. 	pair<int,int>l2;
  33. 	if(i>end || j<beg)
  34. 		return make_pair(INT_MAX,0);
  35. 	if(beg>=i && end<=j)
  36. 		return make_pair(seg[p].ch,seg[p].pos);
  37. 	mid=beg+(end-beg)/2;
  38. 	l1=query(beg,mid,i,j,2*p);
  39. 	l2=query(mid+1,end,i,j,2*p+1);
  40. 	if(l1.first<l2.first)
  41. 		return l1;
  42. 	else if(l1.first==l2.first && l1.second>l2.second)
  43. 		return l1;
  44. 	else
  45. 		return l2;
  46. }
  47. void update(int beg,int end,int i,int j,pair<int,int> value,int p)
  48. {
  49. 	if(i>end || j<beg)
  50. 		return;
  51. 	if(beg>=i && end<=j)
  52. 	{
  53. 		seg[p].ch=value.first;
  54. 		seg[p].pos=value.second;
  55. 		return;
  56. 	}
  57. 	int mid=beg+(end-beg)/2;
  58. 	update(beg,mid,i,j,value,2*p);
  59. 	update(mid+1,end,i,j,value,2*p+1);
  60. 	pair<int,int>l1=make_pair(seg[2*p].ch,seg[2*p].pos);
  61. 	pair<int,int>l2=make_pair(seg[2*p+1].ch,seg[2*p+1].pos);
  62. 	if(l1.first<l2.first)
  63. 	{
  64. 		seg[p].ch=l1.first;
  65. 		seg[p].pos=l1.second;
  66. 	}
  67. 	else if(l1.first==l2.first && l1.second>l2.second)
  68. 	{
  69. 		seg[p].ch=l1.first;
  70. 		seg[p].pos=l1.second;
  71. 	}
  72. 	else
  73. 	{
  74. 		seg[p].ch=l2.first;
  75. 		seg[p].pos=l2.second;
  76. 	}
  77. }
  78. void init1(int st,int end,int p)
  79. {
  80. 	int mid;
  81. 	if(st==end)
  82. 	{
  83. 		seg1[p].ch=INT_MAX;
  84. 		seg1[p].pos=-1;
  85. 	}
  86. 	else
  87. 	{
  88. 		mid=st+(end-st)/2;
  89. 		init1(st,mid,2*p);
  90. 		init1(mid+1,end,2*p+1);
  91. 		seg1[p].ch=INT_MAX;
  92. 		seg1[p].pos=-1;
  93. 	}
  94. }
  95. pair<int,int> query1(int beg,int end,int i,int j,int p)
  96. {
  97. 	int mid;
  98. 	pair<int,int>l1;
  99. 	pair<int,int>l2;
  100. 	if(i>end || j<beg)
  101. 		return make_pair(INT_MAX,0);
  102. 	if(beg>=i && end<=j)
  103. 		return make_pair(seg1[p].ch,seg1[p].pos);
  104. 	mid=beg+(end-beg)/2;
  105. 	l1=query1(beg,mid,i,j,2*p);
  106. 	l2=query1(mid+1,end,i,j,2*p+1);
  107. 	if(l1.first<l2.first)
  108. 		return l1;
  109. 	else if(l1.first==l2.first && l1.second>l2.second)
  110. 		return l1;
  111. 	else
  112. 		return l2;
  113. }
  114. void update1(int beg,int end,int i,int j,pair<int,int> value,int p)
  115. {
  116. 	if(i>end || j<beg)
  117. 		return;
  118. 	if(beg>=i && end<=j)
  119. 	{
  120. 		seg1[p].ch=value.first;
  121. 		seg1[p].pos=value.second;
  122. 		return;
  123. 	}
  124. 	int mid=beg+(end-beg)/2;
  125. 	update1(beg,mid,i,j,value,2*p);
  126. 	update1(mid+1,end,i,j,value,2*p+1);
  127. 	pair<int,int>l1=make_pair(seg1[2*p].ch,seg1[2*p].pos);
  128. 	pair<int,int>l2=make_pair(seg1[2*p+1].ch,seg1[2*p+1].pos);
  129. 	if(l1.first<l2.first)
  130. 	{
  131. 		seg1[p].ch=l1.first;
  132. 		seg1[p].pos=l1.second;
  133. 	}
  134. 	else if(l1.first==l2.first && l1.second>l2.second)
  135. 	{
  136. 		seg1[p].ch=l1.first;
  137. 		seg1[p].pos=l1.second;
  138. 	}
  139. 	else
  140. 	{
  141. 		seg1[p].ch=l2.first;
  142. 		seg1[p].pos=l2.second;
  143. 	}
  144. }
  145. int main() 
  146. {
  147. 	string str;
  148. 	cin>>n>>k>>str;
  149. 	l=str.size();
  150. 	init(1,l,1);
  151. 	init1(1,l,1);
  152. 	for(i=0;i<l;i++)
  153. 		update(1,l,i+1,i+1,make_pair(int(str[i])-96,i+1),1);
  154. 	for(i=0;i<l;i++)
  155. 	{
  156. 		pair<int,int>p1=query(1,l,i+2,l,1);
  157. 		int yu=int(str[i])-96;
  158. 		int lp=0;
  159. 		if(vis[i]==0)
  160. 			lp+=1;
  161. 		if(vis[p1.second-1]==0)
  162. 			lp+=1;
  163. 		if((k>=2 && p1.first<yu) || (k==1 && (lp==1 || lp==0) && p1.first<yu) || (lp==0 && p1.first<yu))
  164. 		{
  165. 			k-=lp;
  166. 			vis[i]=1;
  167. 			vis[p1.second-1]=1;
  168. 			char yo=str[i];
  169. 			str[i]=str[p1.second-1];
  170. 			str[p1.second-1]=yo;
  171. 			update(1,l,i+1,i+1,make_pair(int(str[i])-96,i+1),1);
  172. 			update(1,l,p1.second,p1.second,make_pair(int(str[p1.second-1])-96,p1.second),1);
  173. 			update1(1,l,i+1,i+1,make_pair(int(str[i])-96,i+1),1);
  174. 			update1(1,l,p1.second,p1.second,make_pair(int(str[p1.second-1])-96,p1.second),1);
  175. 		}
  176. 		else if(k==1 && lp==2)
  177. 		{
  178. 			pair<int,int>p1=query1(1,l,i+2,l,1);
  179. 			int yu=int(str[i])-96;
  180. 			if(p1.first<yu)
  181. 			{
  182. 				k=0;
  183. 				vis[i]=1;
  184. 				vis[p1.second-1]=1;
  185. 				char yo=str[i];
  186. 				str[i]=str[p1.second-1];
  187. 				str[p1.second-1]=yo;
  188. 				update(1,l,i+1,i+1,make_pair(int(str[i])-96,i+1),1);
  189. 				update(1,l,p1.second,p1.second,make_pair(int(str[p1.second-1])-96,p1.second),1);
  190. 				update1(1,l,i+1,i+1,make_pair(int(str[i])-96,i+1),1);
  191. 				update1(1,l,p1.second,p1.second,make_pair(int(str[p1.second-1])-96,p1.second),1);
  192. 			}
  193. 		}
  194. 	}
  195. 	vector<int>v1;
  196. 	vector<char>v2;
  197. 	for(i=0;i<l;i++)
  198. 	{
  199. 		cout<<vis[i]<<" ";
  200. 		if(vis[i]==0)
  201. 			continue;
  202. 		v1.push_back(i);
  203. 		v2.push_back((str[i]));
  204. 	}
  205. 	sort(v2.begin(),v2.end());
  206. 	for(i=0;i<v1.size();i++)
  207. 		str[v1[i]]=v2[i];
  208. 	cout<<str;
  209. 	return 0;
  210. }
Success #stdin #stdout 0s 175296KB
comments (?)
stdin
copy 
7 3
acbdaxa
stdout
copy 
0 1 0 1 0 0 1 aabcaxd
https://ideone.com/rysX90
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!