Submission #1134710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134710		bpptidp	Treasure (info1cup19_treasure)	C++20	100 / 100	2 ms	1492 KiB

treasure

#include<bits/stdc++.h>
using namespace std;

bool ok(string&s,int n,int k){
	int len=1;
	for(int i=1;i<n;++i){
		if(s[i]==s[i-1])++len;
		else{
			if(len>=k)return 0;
			len=1;
		}
	}
	return(len<k);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;

    while(1){
    	n=s.size();

	    vector<array<int,2>>bsg;

	    int b[n];
	    memset(b,0x0,sizeof(b));

	    int len=1,l=-1,r=-1;
	    for(int i=1;i<n;++i){
	    	if(s[i]==s[i-1])++len;
	    	else{
	    		if(len>=k){
	    			l=i-len;
	    			r=l+k-1;
	    			//cout<<l<<' '<<r<<'\n';
	    			while(1){
		    			int cnt=0,nwl=l,nwr=r;
		    			for(int j=l-1;j>=max(0,l-k)&&cnt<k;--j){
		    				if(s[j]!=s[l-1])break;
		    				if(b[j])break;
		    				++cnt;
		    				nwl=j;
		    			}
		    			if(cnt==k){
		    				l=nwl;
		    				continue;
		    			}
		    			if(l&&r<n+1&&s[l-1]!=s[r+1]){
		    				cnt=0;
		    				for(int j=r+1;j<=min(n-1,r+k)&&cnt<k;++j){
			    				if(s[j]!=s[r+1])break;
			    				if(b[j])break;
			    				++cnt;
			    				nwr=j;
			    			}
			    			if(cnt==k){
			    				r=nwr;
			    				continue;
			    			}else 
			    				break;
		    			}
		    			for(int j=r+1;j<=min(n-1,r+k)&&cnt<k;++j){
		    				if(s[j]!=s[r+1])break;
		    				if(b[j])break;
		    				++cnt;
		    				nwr=j;
		    			}
		    			if(cnt>=k){
		    				l=nwl;
		    				r=nwr;
		    			}else
		    				break;
		    		}
		    		//cout<<l<<' '<<r<<'\n';
		    		for(int z=l;z<=r;++z)
		    			b[z]=1;
		    		//bsg.push_back({l,r});
		    		i=r+1;
	    		}
	    		len=1;
	    	}
	    }

	    if(len>=k){
	    	int i=n;
		    l=i-len;
			r=l+k-1;
			//cout<<l<<' '<<r<<'\n';
			while(1){
				int cnt=0,nwl=l,nwr=r;
				for(int j=l-1;j>=max(0,l-k)&&cnt<k;--j){
					if(s[j]!=s[l-1])break;
					if(b[j])break;
					++cnt;
					nwl=j;
				}
				if(cnt==k){
					l=nwl;
					continue;
				}
				if(l&&r<n+1&&s[l-1]!=s[r+1]){
					cnt=0;
					for(int j=r+1;j<=min(n-1,r+k)&&cnt<k;++j){
						if(s[j]!=s[r+1])break;
						if(b[j])break;
						++cnt;
						nwr=j;
					}
					if(cnt==k){
						r=nwr;
						continue;
					}else 
						break;
				}
				for(int j=r+1;j<=min(n-1,r+k)&&cnt<k;++j){
					if(s[j]!=s[r+1])break;
					if(b[j])break;
					++cnt;
					nwr=j;
				}
				if(cnt>=k){
					l=nwl;
					r=nwr;
				}else
					break;
			}
			//cout<<l<<' '<<r<<'\n';
			for(int z=l;z<=r;++z)
				b[z]=1;
			//bsg.push_back({l,r});
			i=r+1;
		}

	    /*for(auto&[l,r]:bsg){
	    	for(int i=l;i<=r;++i)
	    		b[i]=1;
	    }*/

	    int bck=0;
	    for(int i=n-1;i>=0;--i){
	    	if(s[i]!=s[n-1])break;
	    	++bck;
	    }

	    int bckk=bck;
	    bck=(bck/k)*k;

	    string s2="";
	    for(int i=0;i<n;++i){
	    	if(i>=n-bckk&&i<n-bckk+bck)continue;
	    	if(!b[i])
	    		s2.push_back(s[i]);
	    }

	    s=s2;
	    if(ok(s,n,k)){
	    	cout<<s;
	    	return 0;
	    }
	}
}

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65