SevenAlarm's blog

By SevenAlarm, history, 7 months ago, In English

Hi! This is my first ever post on Codeforces XD I've solved 484A - Bits this problem and it works fine with the tastcases given in the submission details in my own compiler (I'm using vscode) but is apparently giving different outputs on Codeforces' judge. And the difference is like, off by 1!

I've attached the screenshots from 1)cf output & 2)my original output also here's my code:

#include <bits/stdc++.h>

using namespace std;
long long l, r;
long long p, ans = 0; // ans = 32

int main()
{
    int n, lg1, lg2;


    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l >> r; // 38 , 63
        lg1 = log2(l); // 5
        lg2 = log2(r); // 5

        if (lg1 != lg2)
        {
            if (r == pow(2, lg2 + 1) - 1)
            {
                ans = pow(2, lg2 + 1) - 1;
            }
            else
            {
                ans = pow(2, lg2) - 1;
            }
        }
        else
        {
            if (r == l)
            {
                ans = l;
            }
            else
            {
                int i = lg1; // i = 5 ,
                ans = 0;
                while (lg1 == lg2)
                {
                    p = pow(2, i); // 32
                    if (l >= p)
                        ans += p;
                    l %= p;        // 6
                    r %= p;        // 31
                    lg1 = log2(l); // 2
                    lg2 = log2(r); // 4
                    i--;
                }

                if (r == pow(2, lg2 + 1) - 1)
                {
                    ans += r;
                }
                else
                {
                    ans += pow(2, lg2) - 1;
                }
            }
        }

        cout << ans << endl;
    }
}

I'm assuming there's some problem with the values being very large, since the bug happens with the 18 digit testcase lol. Could there be some memory trick that I can do? I'm relatively new to the c++ community and would be very happy to get ur tips.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SevenAlarm (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read the problem or checked for other issues carefully but your problem is likely that the pow function works with doubles and is thus imprecise. When working with integers, write your own exponentiation function or, for the case of powers of two, use bit shifting, e.g. 1ll << lg2.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sawti safiri bulbuli