fork download
copy 
  1. #include<cstdlib>
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<map>
  6. #include<vector>
  7. #include<algorithm>
  8. struct SCD
  9. {
  10.     int sum;
  11.     int ways;
  12. };
  13. SCD scd[17000000];  // stores sum of array C and D, and number of ways to obtain the sum
  14. int cmp(const void *a, const void *b)
  15. {
  16.     return(*(int *)a-*(int *)b);
  17. }
  18.  
  19. bool compare(const SCD &a, const SCD &b)
  20. {
  21.     return(a.sum<b.sum);
  22. }
  23. int readint() //fast I/O utility function
  24.     {
  25.        char cc = getc(stdin);
  26.        int multiplier=1;
  27.        if(cc=='-'){
  28.         multiplier=-1;
  29.         cc=getc(stdin);
  30.        }
  31.        for (;cc < '0' || cc > '9';)  cc = getc(stdin);
  32.        int ret = 0;
  33.        for (;cc >= '0' && cc <= '9';)
  34.        {
  35.           ret = ret * 10 + cc - '0';
  36.           cc = getc(stdin);
  37.        }
  38.       return ret*multiplier;
  39. }
  40. using namespace std;
  41. int sab[17000000]={0}; // stores sum of array A and B
  42.    int o_sab[17000000]={0}; // stores the ways to obtain the sum of array A and B
  43. int f_scd[17000000]={0}; // stores the final array of sum of integers in C and D array, without repeatition
  44. int o_scd[17000000]={0}; // stores the ways to obtain the sum of array A and B
  45. int main()
  46. {
  47.    int A[4010];
  48.    int B[4010];
  49.    int C[4010];
  50.    int D[4010];
  51.     int r_a[4010]={0};  // stores repeatition/frequency  of array elements in array A
  52.     int r_b[4010]={0};
  53.     int r_c[4010]={0};
  54.     int r_d[4010]={0};
  55.     int i,j,k,l,m,n,a,b,c,d;
  56.     n=readint();
  57.     for(i=0;i<n;i++)
  58.     {
  59.         a=readint();
  60.         b=readint();
  61.         c=readint();
  62.         d=readint();
  63.        A[i]=a, B[i]=b, C[i]=c, D[i]=d;
  64.     }
  65.     qsort(A,n,sizeof(int),cmp);
  66.     qsort(B,n,sizeof(int),cmp);
  67.     qsort(C,n,sizeof(int),cmp);
  68.     qsort(D,n,sizeof(int),cmp);
  69.     int f_A[4010]={0},f_B[4010]={0}, f_C[4010]={0}, f_D[4010]={0};
  70.  
  71.     int i_a=0, i_b=0, i_c=0, i_d=0;
  72.     f_A[i_a]=A[0];
  73.     r_a[i_a]++;
  74.     i_a++;
  75.  
  76.     for(i=1;i<n;i++) // obtaining the final array f_A from array A without repeatition of elements
  77.     {
  78.         if(f_A[i_a-1]==A[i])
  79.         {
  80.             r_a[i_a-1]++;
  81.         }
  82.         else
  83.         {
  84.             f_A[i_a]=A[i];
  85.             r_a[i_a]++;
  86.             i_a++;
  87.         }
  88.     }
  89.  
  90.     f_B[i_b]=B[0];
  91.     r_b[i_b]++;
  92.     i_b++;
  93.  
  94.         for(i=1;i<n;i++)
  95.     {
  96.         if(f_B[i_b-1]==B[i])
  97.         {
  98.             r_b[i_b-1]++;
  99.         }
  100.         else
  101.         {
  102.             f_B[i_b]=B[i];
  103.             r_b[i_b]++;
  104.             i_b++;
  105.         }
  106.     }
  107.  
  108.       f_C[i_c]=C[0];
  109.     r_c[i_c]++;
  110.     i_c++;
  111.  
  112.         for(i=1;i<n;i++)
  113.     {
  114.         if(f_C[i_c-1]==C[i])
  115.         {
  116.             r_c[i_c-1]++;
  117.         }
  118.         else
  119.         {
  120.             f_C[i_c]=C[i];
  121.             r_c[i_c]++;
  122.             i_c++;
  123.         }
  124.     }
  125.  
  126.       f_D[i_d]=D[0];
  127.     r_d[i_d]++;
  128.     i_d++;
  129.  
  130.         for(i=1;i<n;i++)
  131.     {
  132.         if(f_D[i_d-1]==D[i])
  133.         {
  134.             r_d[i_d-1]++;
  135.         }
  136.         else
  137.         {
  138.             f_D[i_d]=D[i];
  139.             r_d[i_d]++;
  140.             i_d++;
  141.         }
  142.     }
  143.  
  144.     int i_sab=0;
  145.     for(i=0;i<i_a;i++)
  146.     {
  147.         for(j=0;j<i_b;j++)
  148.         {
  149.             sab[i_sab]=f_A[i]+f_B[j];
  150.             o_sab[i_sab]=r_a[i]*r_b[j];
  151.             i_sab++;
  152.         }
  153.     }
  154.  
  155.  
  156.     int i_scd=0;
  157.     for(i=0;i<i_c;i++) // store the number of ways to obtain sum of integers in list C and D and sum of array elements
  158.     {
  159.         for(j=0;j<i_d;j++)
  160.         {
  161.             scd[i_scd].sum=f_C[i]+f_D[j];
  162.            scd[i_scd].ways=r_c[i]*r_d[j];
  163.             i_scd++;
  164.         }
  165.     }
  166.  
  167.     sort(&scd[0], &scd[i_scd], compare);
  168.  
  169.     int fi_scd=0;
  170.     f_scd[fi_scd]=scd[0].sum; // stores first sum of C and D for matching with other sums
  171.     o_scd[fi_scd]+=scd[0].ways; // stores number of ways to generate the sum
  172.     fi_scd++;
  173.  
  174.     for(i=1;i<i_scd;i++)
  175.     {
  176.         if(f_scd[fi_scd-1]==scd[i].sum)
  177.         {
  178.             o_scd[fi_scd-1]+=scd[i].ways;  // sotres number of ways to obtain a sum
  179.         }
  180.         else
  181.         {
  182.             f_scd[fi_scd]=scd[i].sum; // stores new sum without repeatition
  183.             o_scd[fi_scd]+=scd[i].ways;
  184.             fi_scd++;
  185.         }
  186.     }
  187.  
  188.  
  189.     int ans=0;
  190.     for(i=0;i<i_sab;i++)
  191.     {
  192.         int low=0, high,mid;
  193.         high=fi_scd-1;
  194.         mid=(low+high)/2;
  195.         while(low<=high) // binary search
  196.         {
  197.             mid=(low+high)/2;
  198.             if(sab[i]+f_scd[mid]==0)
  199.             {
  200.                 ans+=o_sab[i]*o_scd[mid];
  201.                 break;
  202.             }
  203.             else if(sab[i]+f_scd[mid]>0)
  204.                 high=mid-1;
  205.             else if(sab[i]+f_scd[mid]<0)
  206.                 low=mid+1;
  207.         }
  208.     }
  209.     printf("%d\n",ans); // print ans , yet SIGKILL :(
  210.     return(0);
  211. }
  212.  
Success #stdin #stdout 0s 401856KB
comments (?)
stdin
copy 
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
stdout
copy 
256
https://ideone.com/WWEjN8
language:
C++ (gcc 8.3)
created:
9 years 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!