Submission #229575

#	Time	Username	Problem	Language	Result	Execution time	Memory
229575		blacktulip	Treasure (info1cup19_treasure)	C++17	0 / 100	5 ms	384 KiB

treasure

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
 
int n,m,k,flag,t,d[li],fa[li];
int cev;
bool vis[li];
string s;
 
inline int dsu(int x){
	if(x==fa[x])return x;
	return fa[x]=dsu(fa[x]);
} 

int main(void){
	fio();
	//~ freopen("simple.txt","r",stdin);
	cin>>n>>k>>s;
	//~ for(int jjj=1;jjj<=min(6,(int)sqrt(n)+5);jjj++){
		int say=1;
		d[0]=1;
		for(int i=0;i<=n;i++)fa[i]=i;
		for(int i=1;i<(int)s.size();i++){
			if(s[i]==s[i-1])say++;
			else say=1;
			if(s[i]==s[dsu(i-1)])d[i]=d[dsu(i-1)]+1;
			else d[i]=1;
			//~ cout<<d[i]<<endl;
			if(d[i]==k){
				say=k;
				while(say>0){
					vis[dsu(i-k+1+say-1)]=1;
					if(i-k>=0)
					fa[dsu(i-k+1+say-1)]=dsu(i-k);
					//~ s.erase(s.begin()+i-k+1);
					d[dsu(i-k+1+say-1)]=1;
					say--;
				}
				//~ i-=k;
				//~ i--;
			}
			//~ cout<<s[i]<<" : ; "<<i<<endl;
		}
		
	//~ }
	for(int i=0;i<n;i++){
		if(vis[i])continue;
		cout<<s[i];
	}
	//~ cout<<s<<endl;
	return 0;
}

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