#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;
it=st.begin();
for(;it!=st.end();it++){
//~ cout<<*it<<endl;
cout<<s[*it];
}
//~ std::cout<<"printf: "<< duration <<'\n';
return 0;
}
Compilation message
treasure.cpp: In function 'int main()':
treasure.cpp:37:12: warning: variable 'duration' set but not used [-Wunused-but-set-variable]
double duration;
^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
