fork(2) download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<queue>
  4. using namespace std;
  5. int n;
  6. char a[1000009];
  7. struct A{
  8.     int l,r,d;
  9.     bool operator<(const A& rhs)const{
  10.         if(l-rhs.l)return l>rhs.l;
  11.         return d>rhs.d;
  12.     }
  13. };
  14. int main(){
  15.     int i,j,k;
  16.     scanf("%d",&n);
  17.     scanf("%s",a);
  18.     int res=0;
  19.     int ll=0;
  20.     priority_queue<A> tq;
  21.     for(i=0;i<n;){
  22.         if(a[i]=='1'){
  23.             i++;
  24.             continue;
  25.         }
  26.         for(j=i;j<n;j++){
  27.             if(a[j]=='1')break;
  28.         }
  29.         int l,r,d;
  30.         d=(j-i)<<1;
  31.         l=((j+1)&(-2))-d;
  32.         if(l<0)l=0;
  33.         r=i&(-2);
  34.         tq.push({l,r,d});
  35.         i=j;
  36.     }
  37.     while(ll<n&&!tq.empty()){
  38.         A tt=tq.top();
  39.         tq.pop();
  40.  
  41.         printf("%d %d %d , %d %d\n",tt.l,tt.r,tt.d,ll,res);
  42.         int tl=ll;
  43.         if(ll>tt.l){
  44.             if(ll<=tt.r){
  45.                 tq.push({ll,tt.r,tt.d});
  46.             }
  47.             else{
  48.                 tl=tt.r+tt.d;
  49.                 if(ll<tl)ll=tl;
  50.             }
  51.             continue;
  52.         }
  53.         if(ll<tt.l){
  54.             res+=(tt.l-ll);
  55.             tl=tt.l;
  56.         }
  57.         if(tl>tt.r)tl=tt.r;
  58.         tl+=tt.d;
  59.         if(ll<tl){
  60.             ll=tl;
  61.         }
  62.     }
  63.     if(ll<n){
  64.         res+=(n-ll);
  65.     }
  66.     printf("%d\n",res>>1);
  67. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
12
111010000111
stdout
copy 
2 2 2 , 0 0
2 4 8 , 4 2
4 4 8 , 4 2
1
https://ideone.com/ZkefbV
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 days ago
visibility:
public

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!