WA

Ben's fortune predict system is successfully developed!

The predict system is a distributed system consists of $N$ computers. When it receives a predict request, each computer will generate one lower case letter as its output. The final fortune predict result is determined by the concentration of all $N$ outputs.

Tired of getting good predictions like $\text{suitable for writing codes}$ or $\text{will get accepted for every problem}$ , Crystal decided to hack into the predict system and modify the predict result. He has already got the access permission of every computer in the predict system, so he could modify their output to any letter arbitrarily.

As Crystal is not going to take part in ICPC World Final 2077, he want unlucky predictions like $\text{awful: millions of bugs}$ . He found that the more substrings $\text{aa}$ occurs in the concentration of all $N$ outputs, the unluckier he will get in the end. But as the contest is coming soon, he only has time to modify at most $K$ outputs of the computers in the predict system.
As Crystal is busy hacking into the system, could you tell him how to get the most $\text{aa}$ substrings after his modification?

Output two lines. The first line contains a single integer, denotes the maximum number of $\text{aa}$ substring Crystal can get, after his modification. The second line contains the final modified predict string, if there are multiple ways that results in the maximum number of $\text{aa}$ substring, print any.

Note that you don't have to minimize the number of $\text{ac}$ substring.

#include <bits/stdc++.h> using namespace std; typedef long long ll; int i,j,k,n,m; struct sb{ int l,r,w; bool operator<(const sb x)const{return w>x.w;} }s; priority_queue<sb> q; char c[500500]; int main(){ ios::sync_with_stdio(0); cin>>n>>m>>c+1; for(i=1;i<=n;i++){ if(c[i]=='a'){ if(j){ s.l=j+1;s.r=i-1;s.w=i-j-1; q.push(s); } j=i; } } while(!q.empty()){ s=q.top();q.pop(); if(s.w>m){break;} m-=s.w; for(i=s.l;i<=s.r;i++){ c[i]='a'; } } if(!j&&m){ c[1]='a';m--; } for(i=1;i<=n;i++){ if(m&&c[i]!='a'&&c[i-1]=='a'){ c[i]='a';m--; } } for(i=1;i<=n;i++){ if(c[i]=='a'&&c[i-1]=='a'){k++;} } cout<<k<<endl<<c+1; }

详情