fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
  3. #define ll long long
  4. using namespace std;
  5.  
  6. long long pre_sum(long long start,long long endd)
  7. {
  8.     return((endd-start+1)*(endd+start)/2);
  9. }
  10.  
  11. int main()
  12. {
  13.     fast
  14.     int t;
  15.     cin>>t;
  16.     while(t--)
  17.     {
  18.         ll n,k;
  19.         cin>>n>>k;
  20.         n=(n-1+k);
  21.         ll total = ((n-k+1)*(k+n))/2;
  22.         ll key =total/2;
  23.  
  24.         ll left=k,right=n;
  25.         while (left < right)
  26.         {
  27.             int mid = left + (right - left) / 2;
  28.  
  29.             if ( pre_sum(k,mid)> key)
  30.                 right = mid;
  31.             else
  32.                 left = mid + 1;
  33.         }
  34.         ll sum1=(pre_sum(k,right)); // try the sum that larger than total/2
  35.         ll sum2=(pre_sum(k,right-1));// try the sum that smaller than total/2
  36.         cout<<min(abs((total-sum1)-sum1),abs((total-sum2)-sum2))<<"\n"; //minimum between both sums
  37.     }
  38. }
  39.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
2 2
7 2
5 3
1000000000 1000000000
stdout
copy 
1
5
1
347369930
https://ideone.com/NhosuC
language:
C++ (gcc 8.3)
created:
12 days 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!