fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int n,k;
  29. char str[MAX];
  30. int pre[MAX],suf[MAX];
  31. int w[MAX],num[MAX];
  32. int pre2[MAX],suf2[MAX];
  33.  
  34. int q[MAX*3],head,end,is[MAX];
  35.  
  36. void del(int pre[MAX],int suf[MAX],int u)
  37. {
  38.     suf[pre[u]]=suf[u];
  39.     pre[suf[u]]=pre[u];
  40. }
  41.  
  42. int ans[MAX],top,answer[MAX];
  43.  
  44. int main()
  45. {
  46. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  47.     scanf("%d%d",&n,&k);
  48.     scanf("%s",str+1);
  49.     int last=0,i;
  50.     for(int i=1;i<=n;++i)
  51.         if(str[i]=='c')
  52.         {
  53.             pre[i]=last;
  54.             suf[last]=i;
  55.             num[i]=i-1-last;
  56.             last=i;
  57.         }
  58.     pre[0]=last;
  59.     num[0]=n-last;
  60.  
  61.     for(int i=1;i<=n;++i)
  62.     {
  63.         suf2[i]=i+1;
  64.         pre2[i]=i-1;
  65.     }
  66.     suf2[n]=0;
  67.  
  68.     for(int i=suf[0];i;i=suf[i])
  69.     {
  70.         w[i]=num[i]+num[suf[i]];
  71.         is[i]=1;
  72.         if(w[i]>=k)
  73.             q[end++]=i;
  74.     }
  75.  
  76.     while(head<end)
  77.     {
  78.         int u=q[head++];
  79.         if(!is[u] || w[u]<k)
  80.             continue;
  81.         int res=k,tot=0;
  82.         for(i=pre2[u];i && res && str[i]!='c';i=pre2[i])
  83.         {
  84.             --res;
  85.             --num[u];
  86.             ans[++tot]=i;
  87.         }
  88.         reverse(ans+1,ans+tot+1);
  89.         ans[++tot]=u;
  90.         for(i=suf2[u];i && res;i=suf2[i])
  91.         {
  92.             --res;
  93.             --num[suf[u]];
  94.             ans[++tot]=i;
  95.         }
  96.         num[suf[u]]+=num[u];
  97.         REP(i,1,tot)
  98.         {
  99.             del(pre2,suf2,ans[i]);
  100.             answer[++top]=ans[i];
  101.         }
  102.         is[u]=0;
  103.         if(pre[u])
  104.         {
  105.             w[pre[u]]=num[pre[u]]+num[suf[u]];
  106.             q[end++]=pre[u];
  107.         }
  108.         if(suf[u])
  109.         {
  110.             w[suf[u]]=num[suf[u]]+num[suf[ suf[u] ]];
  111.             q[end++]=suf[u];
  112.         }
  113.         del(pre,suf,u);
  114.     }
  115.  
  116.     for(i=top-k;i>0;i-=k+1)
  117.     {
  118.         for(int j=i;j<=i+k;++j)
  119.             printf("%d ",answer[j]);
  120.         printf("\n");
  121.     }
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0s 51152KB
comments (?)
stdin
copy 
12 2
ccbcbbbbbbcb
stdout
copy 
1 8 12 
2 6 7 
9 10 11 
3 4 5
https://ideone.com/XzeiMm
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!