CHFING - same code (almost) but only one gave AC

Here are 2 submissions of a friend:

AC: https://www.codechef.com/viewsolution/24673271
WA: https://www.codechef.com/viewsolution/24671781

Code with AC uses 128bit int. It got accepted. How? Does codechef server runs on 128bit processor?

1 Like

128 bit integer is enough to calculate your ans when / by 2 but long long int gets out of bounds and when / 2 your ans may not be integer so modulo 1e7+9 gives wa when we take very large no . To solve issue we use modulo multiplicative inverse or find even term and divide it by 2
Hope it helps :smile:

I know 128bit is enough. But Isn’t 64bit (ie long long) is the maximum limit servers should have?
Most of the computer can handle up till 64bit.
Do they use 128bit processors?

Any number of bits processor can compute any number of bits integer.
Using code ( which is built in c++ for 128 bit int)
They use multiple operations for each operation __int128
That doesn’t require 128 bit processor

2 Likes

Its because ll is not enough to store and answer overflows. Once it overflows you cannot recover it again.
whereas 128bit are enough

1 Like

for example they will use two add operations of 64 bit for adding 128 bits in total.
similar for other operations.

1 Like

And does cin cout work with 128bit?
will I have to typecast it to longlong?

looking nice in 6 stars !! :stuck_out_tongue::stuck_out_tongue:

1 Like

Thanks :slight_smile:

It won’t work.
You will have to either type cast (if resultant value doesn’t overflow) or convert it into string to print it

1 Like