Submission #39195896

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
/*define about others*/
#define ls(k) k<<1
#define rs(k) k<<1|1
#define lson(k) l,mid,ls(k)
#define rson(k) mid+1,r,rs(k)
#define sizea(x,d) x+1,x+d+1
#define all(x) x.begin(),x.end()
#define lowbit(x) (x&-x)
/*define about variable*/
#define re register
#define il inline
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
/*define about pair*/
#define np pair<int,int>
#define tup pair<int,pair<int,int> >
#define mp(a,b) make_pair(a,b)
#define mpp(a,b,c) make_pair(a,make_pair(b,c))
#define fi first
#define se second
#define _1 first
#define _2 second.first
#define _3 second.second
/*define about loop*/
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define repe(u) for(int i=head[u];i;i=e[i].nxt)
#define repv(i,s) for(int i:s)
/*define about STL*/
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define ump unordered_map
#define pq priority_queue
#define iter iterator
/*define about function*/
#define clz __builtin_clz
#define ctz __builtin_ctz
#define ppc __builtin_popcount
#define clzl __builtin_clzll
#define ctzl __builtin_ctzll
#define ppcl __builtin_popcountll
/*define about IO*/
//#define EXODUS
//#define online_judge
#ifdef online_judge
#define debug(x) 1428
#define Debug(...) 2857
#else
#define debug(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<'\n'
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace IO{
	il int read(){
		int ans=0,flag=1;
		char ch=getchar();
		while(!isdigit(ch)){if(ch=='-')flag=-1;ch=getchar();}
		while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
		return ans*flag;
	}
	il string reads(){
		string ans="";char ch=getchar();
		while(ch==' '||ch=='\n')ch=getchar();
		while(ch!=' '&&ch!='\n')ans+=ch,ch=getchar();
		return ans;
	}
	il char readc(){
		char ch=getchar();
		while(ch==' '||ch=='\n')ch=getchar();
		return ch;
	}
	il int sqr(int x){return x*x;}
	il void reada(int *a,int len){for(int i=1;i<=len;i++)a[i]=read();}
	void write(int x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
		return;
	}
}
namespace modcalc{
	const int mod=1e9+7/*,998244353,1e9+9*/;
	void fix(int &x){if(x>=mod)x-=mod;else if(x<0)x+=mod;return;}
	void inc(int &x,int y){fix(x+=y);return;}
	void dec(int &x,int y){fix(x-=y);return;}
	void mul(int &x,int y){x=1ll*x*y%mod;return;}
	int rem(int x){if(x>=mod)x-=mod;else if(x<0)x+=mod;return x;}
	int add(int x,int y){return rem(x+y);}
	int del(int x,int y){return rem(x-y);}
	int tim(int x,int y){return 1ll*x*y%mod;}
}
namespace chkmath{
	int chkmin(int &x,int y){x=x>y?y:x;return x;}
	int chkmax(int &x,int y){x=x<y?y:x;return x;}
	int chkeql(int &x,int y){x=y;return x;}
}
//using namespace modcalc;
using namespace chkmath;
using namespace IO;

bool mem1=0;
int Datas=0,T=1;

const int N=2e5+7;
int n,K;
char s[N];
int val[N];
bool vis[N];
pq<np>q;

bool mem2=0;

void calc(){
	int ans=0;
	fprintf(stderr,"%s\n",s+1);
	for(int i=1;i<n;i++)
		if(s[i]==s[i+1]&&s[i]=='Y')ans++;
	printf("%d\n",ans);
}

void Main(){
	n=read(),K=read();
	scanf("%s",s+1);
	int bg=1,ed=n;
	while(s[bg]=='X'&&bg<=n)bg++;
	while(s[ed]=='X'&&ed>=1)ed--;
	if(bg>ed)return printf("%d\n",max(0,K-1)),void();
	for(int l=bg,r=l;l<=ed;l=r){
		while(s[l]==s[r]&&r<=ed)r++;
		for(int i=l;i<r;i++){
			val[i]=(r-l);
			if(s[l]=='X')q.push(mp(-val[i],i));
		}
	}
//	for(int i=1;i<=n;i++)
//		Debug("%d ",val[i]);
//	Debug("\n");
	while(!q.empty()&&K){
		K--;auto [v,i]=q.top();q.pop();
		s[i]='Y',vis[i]=1;
	}
	if(!K)return calc();
	for(int i=1;i<bg;i++)q.push(mp(i-bg,i));
	for(int i=ed+1;i<=n;i++)q.push(mp(ed-i,i));
	while(!q.empty()&&K){
		K--;auto [v,i]=q.top();q.pop();
		s[i]='Y',vis[i]=1;
	}
	if(!K)return calc();
	for(int i=1;i<=n;i++){
		if(!vis[i])q.push(mp(val[i],-i));
		else break;
	}
	while(!q.empty()&&K){
		K--;auto [v,i]=q.top();q.pop();
		s[-i]='X',vis[-i]=1;
	}
	if(!K)return calc();
	for(int i=n;i>=1;i--){
		if(!vis[i])q.push(mp(val[i],i));
		else break;
	}
	while(!q.empty()&&K){
		K--;auto [v,i]=q.top();q.pop();
		s[i]='X',vis[i]=1;
	}
	if(!K)return calc();
	for(int i=1;i<=n;i++){
		if(!vis[i])q.push(mp(val[i],i));
	}
	while(!q.empty()&&K){
		K--;auto [v,i]=q.top();q.pop();
		s[i]='X',vis[i]=1;
	}
	if(!K)return calc();
	assert(0);
	return;
}

int main(){
#ifdef EXODUS
	printf("%.5lfMB\n",abs(&mem2-&mem1)/1024.0/1024.0);
	freopen("Data.in","r",stdin);
	freopen("Code.out","w",stdout);
#endif
#ifdef online_judge
	freopen("Data.in","r",stdin);
	freopen("Code.out","w",stdout);
#endif
	if(Datas)T=read();
	while(T--)Main();
#ifdef EXODUS
	cerr<<clock()<<"ms"<<endl;
#endif
	return 0;
}
//LOJ loyal users:EXODUS
/*
0. Enough array size? Enough array size? Enough array size? Interger overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error? Use The TRUE MODULE?

4. Do not forget to CHECK YOUR CODE before submitting!
Delete the DEBUGGING? Add FILE I/O?
*/

Submission Info

Compile Error

./Main.cpp: In function ‘void Main()’:
./Main.cpp:131:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  131 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~

Judge Result