Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:ft............

Posted by frkstyc at 2006-03-25 03:03:32 on Problem 2785
In Reply To:Re:ft............ Posted by:sza at 2006-03-25 03:02:29
拜托你就改得彻底一些吧……abs64……而且还要另外优化一下常数

> 继续超时,哭。。。。。。。。
> 
> #include <stdio.h>
> #include <stdlib.h>
> int abs64(int a){
>     if(a<0) return -a;else return a;
> }
> int cmp(const void *i,const void *j){
>     return *((const int*)i)-*((const int*)j);
> }
> int numerate1[7800000],numerate2[7800000],a[4001],b[4001],c[4001],d[4001],tem;
> int main(int argc, char *argv[])
> {
>     long index,i,j,k,m,n,counter=0,head,tail,ch,ct,c1,c2;
>     scanf("%d",&n);
>     for(i=0;i<n;i++) scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
>     counter=0;
>     index=0;
>     for(i=0;i<n;i++){
>         for(j=0;j<n;j++){
>             numerate1[index++]=a[i]+b[j];
>         }
>     }
>     index=0;
>     for(i=0;i<n;i++){
>         for(j=0;j<n;j++){
>             numerate2[index++]=c[i]+d[j];
>         }
>     }
>     qsort(numerate1,index,sizeof(int),cmp);
>     qsort(numerate2,index,sizeof(int),cmp); printf("ok\n");
>     head=0;tail=index-1;
>     while(head<index && tail>=0){
>         c1=1;c2=1;
>         if(numerate1[head]+numerate2[tail]==0) {
>             ch=head;ct=tail;
>             while(head<index && numerate1[ch]==numerate1[++head]) c1++;
>             while(tail>=0 && numerate2[ct]==numerate2[--tail]) c2++;
>             counter=counter+c1*c2;
>         }
>         else if(numerate1[head]<=0&&numerate2[tail]>=0){
>             if(abs64(numerate1[head])<abs64(numerate2[tail])) tail--;
>             else head++;
>         }
>         else if(numerate1[head]>=0&&numerate2[tail]<=0){
>             if(abs64(numerate1[head])<abs64(numerate2[tail])) head++;
>             else tail--;
>         }
>         else if(numerate1[head]<=0&&numerate2[tail]<=0){ head++;
>         }
>         else if(numerate1[head]>=0&&numerate2[tail]>=0){ tail--;
>         }
>     }
>     printf("%ld\n",counter);
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator