Submission #229600

#	Time	Username	Problem	Language	Result	Execution time	Memory
229600		blacktulip	Treasure (info1cup19_treasure)	C++17	100 / 100	64 ms	11012 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];
int cev;
set<int> st;
string s;
 
int main(void){
	fio();
	//~ freopen("simple.txt","r",stdin);
	std::clock_t start;
    double duration;
 
    start = std::clock();
	cin>>n>>k>>s;
	for(int i=0;i<n;i++)st.insert(i);
	//~ for(int jjj=1;jjj<=min(6,(int)sqrt(n)+5);jjj++){
		int say=1;
		d[0]=1;
		auto it=st.begin();
		it++;
		for(;it!=st.end();it++){
			int i=*it;
			auto it1=it;
			//~ cout<<*it<<endl;
			
			//~ cout<<i<<endl;
			it1--;
			//~ cout<<*it1<<endl;
			int i1=*it1;
			if(s[i]==s[i1])say++;
			else say=1;
			if(s[i]==s[i1])d[i]=d[i1]+1;
			else d[i]=1;
			//~ cout<<d[i]<<endl;
			if(d[i]>=k){
				say=k;
				auto it2=it;
				it2++;
				while(say>1){say--;it--;}
				it1=it;
				//~ it--;
				//~ it--;
				it=it2;
				it++;
				say=k;
				if(it1!=st.begin())it--;
				st.erase(it1,it2);
				//~ cout<<*it<<endl;
				while(say>0){
					//~ it=st.find()
					//~ cout<<*it<<endl;
					
					d[i-k+1+say-1]=1;
					say--;
				}
				n-=k;
				i-=k;
				//~ cout<<*st.begin()<<endl;
				
				it--;
				
			}
			//~ cout<<st.size()<<endl;
			//~ cout<<s[i]<<" : ; "<<i<<endl;
		}
		
	//~ }
	//~ cout<<s;
	duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
	int tut=0;
	int at=0;
	for(auto it=st.begin();it!=st.end();it++){
		if(tut>=k)break;
		tut++;
		if(s[*it]==s[*st.begin()])at++;
	}
	//~ cout<<at<<" : ; "<<k<<endl;
	if(at==k){
		tut=0;
		for(auto it=st.begin();it!=st.end();it++){
			if(tut>=k)break;
			tut++;
			st.erase(it);
		}
	}
		it=st.begin();
		for(;it!=st.end();it++){
			//~ cout<<*it<<endl;
			cout<<s[*it];
		}
    //~ std::cout<<"printf: "<< duration <<'\n';
	return 0;
}

Compilation message (stderr)

treasure.cpp: In function 'int main()':
treasure.cpp:37:12: warning: variable 'duration' set but not used [-Wunused-but-set-variable]
     double duration;
            ^~~~~~~~

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