Submission #229598

#	Time	Username	Problem	Language	Result	Execution time	Memory
229598		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];
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<=3;jjj++){
		
		//~ 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();){
				//~ cout<<flag<<endl;
				//~ if(flag)it--;
				flag=0;
				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){
					flag=1;
					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--;
					
				}
				else 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);
		}
	}
		auto 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: 0 / 35
• Subtask 2: 0 / 65