> #include <stdio.h>
> #define Maxn 2000
> 
> struct node{
>         __int64    n,b,bn;
>        }m,u,d,l,r,ul,ur,dl,dr;
> 
> struct ansnode{
>         __int64    c,l;
>        }now,ans[Maxn];
>  __int64    ll;
>  __int64    t[Maxn];
>  __int64    c[Maxn];
>  long  n , total;
> 
> __int64   abs( __int64    a){
>      if (a>0) return a;
>      return -a;
>      }
>      
>  __int64    max( __int64    a, __int64    b){
>      if (a<b) a=b;
>      return a;
>      }
> 
>  __int64    max( __int64    a,  __int64    b,  __int64    c,  __int64    d){
>      if (a<b) a=b; 
>      if (a<c) a=c; 
>      if (a<d) a=d;
>      return a;
>      }
> 
>  __int64    min( __int64    a,  __int64    b,  __int64    c,  __int64    d, __int64    e){
>      if (a>b) a=b; 
>      if (a>c) a=c;
>      if (a>d) a=d;
>      if (a>e) a=e;
>      return a;
>      }
> 
> void inp(){
>           long  x,y;
>           n=0;
>           scanf("%ld %ld",&x,&y);
>           while (x!=0 || y!=0) {
>                 n++;
>                 t[n]=y;
>                 c[n]=x;
>                 scanf("%ld %ld",&x,&y);
>                 if (n>1000) break;
>                 }
>           while (x!=0 || y!=0) scanf("%ld %ld",&x,&y);  
>           t[0]=ll;
>           c[0]=0;
>           t[n+1]=ll;
>           t[n+1]=0;
>           }
>      
> void prepare(){
>       __int64    s, i;
>      u.n=-ll+1; u.bn=1; u.b=0;
>      l.n=0;    l.bn=ll; l.b=0;
>      m.n=1;    m.bn=1;  m.b=1;
>      r.n=2;    r.bn=2;  r.b=1;
>     
>      now.c=0;
>      
>      if (t[1]==1){
>         r.n=2;
>         r.bn=1;
>         r.b=2;
>         }
>      s=0; i=0;
>      while (s<=ll || i>n){
>            i++;
>            s+=t[i];
>            }
>      s-=ll;
>      d.n=ll+1; d.bn=t[i]-s+1; d.b=i;
>      
> 
>      if (d.n!=n+1) now.c=max(now.c,abs(c[d.b]-c[m.b]));
> 
>      if (ll!=1) now.c=max(now.c,abs(c[r.b]-c[m.b]));
> 
>      if (d.b!=n+1 && ll!=1) 
>         if (d.bn==t[d.b]) now.c=max(now.c,abs(c[d.b+1]-c[m.b]));
>         
>      now.l=1;
>      c[n+1]=-100000000;
>      t[n+1]=ll;
>      } 
>      
>      
>      
> void promote(node &k,  __int64    l){
>      k.bn+=l;
>      k.n+=l;
>      if (k.bn>t[k.b]){
>         k.b++;
>         k.bn=1;
>         }
>      }
>         
>      
>  __int64    calc(){
>      if (m.b==n+1) return -1;
>       __int64    max1;
>      max1=0; 
>      if (u.b!=0)   max1=max(max1,abs(c[u.b]-c[m.b]));
>      if (l.n%ll!=0)   max1=max(max1,abs(c[l.b]-c[m.b]));
>      if (r.n%ll!=1) max1=max(max1,abs(c[r.b]-c[m.b]));
>      if (d.b!=n+1) max1=max(max1,abs(c[d.b]-c[m.b]));
>      
>      
>      if (m.n>ll){
>         if (u.bn==1 && m.n%ll!=1) max1=max(max1,abs(c[u.b-1]-c[m.b]));
>         if (u.b!=n && u.bn==t[u.b] && m.n%ll!=0) max1=max(max1,abs(c[u.b+1]-c[m.b]));
>         }
>            
>      if (d.b!=n+1){
>         if (d.bn==1 && m.n%ll!=1) max1=max(max1,abs(c[d.b-1]-c[m.b]));
>         if (d.b!=n && d.bn==t[d.b] && m.n%ll!=0) max1=max(max1,abs(c[d.b+1]-c[m.b]));
>         }
>            
>      return max1;
>      }
>      
> void add( __int64    del , __int64    col){
>      if (col==now.c){
>         now.l+=del;
>  
>         return ;
>         }
>      total++;
>      ans[total].c=now.c; 
>      ans[total].l=now.l;
>      
> 
>      now.l=del;
>      now.c=col;
>      }
> 
>      
> void work(){
>      prepare();
>       __int64    del , col;
>      while (1) {
>            del=min(abs(t[m.b]-m.bn),abs(t[u.b]-u.bn),abs(t[d.b]-d.bn),abs(t[l.b]-l.bn),abs(t[r.b]-r.bn));
>            if (m.n>ll){
>                      if (u.bn==1 && m.n%ll!=1) del=0;
>                      if (u.bn==t[u.b] && m.n%ll!=0) del=0;
>                      }
>            
>            if (d.b!=n+1){
>                      if (d.bn==1 && m.n%ll!=1) del=0;
>                      if (d.bn==t[d.b] && m.n%ll!=0) del=0;
>                      }
>            
>            if (del==0) del=1;
>     
>            promote(u,del);
>            promote(d,del);
>            promote(l,del);
>            promote(m,del);
>            promote(r,del);
>            col=calc();
>     
>            add(del,col);
>            if (m.b==n+1) return ;
>            
>            if (total> 1000) return ;
>            }
>      }
>      
>      
> void out(){
>            printf("%I64d\n",ll);
>             long  i;
>            for (i=1; i<=total; i++)      printf("%I64d %I64d\n",ans[i].c, ans[i].l);
>            printf("0 0\n");
>            } 
> 
> int main(){
>      long i;
>   //  freopen("1009.in","r",stdin);
>   //  freopen("1009.out","w",stdout);
>     scanf("%I64d",&ll);
>     while (ll!=0){
>           total=0;
>           inp();
>           if (n>1000){ scanf("%I64d",&ll); continue; }
>           work();
>           if (total<=1000) out();
>           scanf("%I64d",&ll);
>           }
>     printf("0\n");
>   //  fclose(stdout);
>     return 0;
> }

• Re:小人写了个o(n) 的程序，sample 过了，但是莫名的run time error...... 那位大牛能帮帮忙？不胜感谢（如果有测试数据，请发到qmczcn@sohu.com) (0) darklord 2006-11-27 21:46:33
• Re:小人写了个o(n) 的程序，sample 过了，但是莫名的run time error...... 那位大牛能帮帮忙？不胜感谢（如果有测试数据，请发到qmczcn@sohu.com) (0) lshguang89 2008-07-15 15:25:26