Блог пользователя ChaituBoi

Автор ChaituBoi, 4 года назад, По-английски

Now what i did was similar to editorial. The problem isnt with the approach but with the fact that if use operation ans+=(n*(n-1))/2 i get wrong answer due to integer overflow, now I AM using long long but still it gives -ve answer in 2nd test case which is ofcourse due to overflow. To solve this what i did was first divide n or (n-1) by 2 (depending upon parity) and then multiplying and got answer accepted. Can someone tell why this is happening?? I know i would probably be a very dumb mistake but plz dont judge harshly. :D

MY CODE:

#include<bits/stdc++.h>

using namespace std;

//void swap(int &a,int &b){

// int tmp=a;a=b;b=tmp;

//}

int size(long long a){

int n=0;

while(a!=0){

n++;

a/=2;

}

return n;

}

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t,n;

cin>>t;

while(t--){

cin>>n;

long long A[n],ans=0;

for(int i=0;i<n;i++)cin>>A[i];

` `

vector<int>nums(32,0);

for(int i=0;i<n;i++){

nums[size(A[i])]++;

}

for(int i=0;i<32;i++){

// long long a=nums[i],b=nums[i]-1;

// if(nums[i]%2==0){

// a/=2;

// }

// else{

// b/=2;

// }

// ans+=(a*b);

ans+=((nums[i]*(nums[i]-1))/2);

}

cout<<ans<<"\n";

}

` `

return 0;

}

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Try with a vector of long long.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That worked, but i am curious that vector should be sufficient since there are only 10^5 elements in total and i am using the vector to store number of occurences (with size i) which obviously can't be more than 10^5 for any test case!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      nums[i]*(nums[i]-1) overflows the int limit when nums[i]=10^5.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        whether the answer overflows or not, doesn't it depend on the size of containor which is long long , in this case. Or it does on the operands too?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          nums[i] is an int, so multiplying two of them yields an int, which overflows. The value (which has overflowed) is stored as a long long, but since it overflowed the answer is wrong.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Thank you for solving my tasks!