fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     // Precompute step sizes S[1..30]
  10.     vector<ll> S;
  11.     S.push_back(0); // S[0] unused
  12.     S.push_back(2); // S[1]=2
  13.     for(int k=2; k<=30; ++k){
  14.         S.push_back(2*S[k-1] +1);
  15.     }
  16.     int Q;
  17.     cin >> Q;
  18.     while(Q--){
  19.         ll x, y;
  20.         cin >> x >> y;
  21.         // Find smallest k where S[k] >=x
  22.         int k=1;
  23.         for(; k<=30; ++k){
  24.             if(S[k] >=x){
  25.                 break;
  26.             }
  27.         }
  28.         if(k >30){
  29.             // Should not happen as S[30] ~1.6e9 >=1e9
  30.             cout << "1\n";
  31.             continue;
  32.         }
  33.         if(k ==1){
  34.             // Step1: all red
  35.             cout << "1\n";
  36.             continue;
  37.         }
  38.         ll S_prev = S[k-1];
  39.         ll y_center = S_prev +1;
  40.         ll x_prime = x - S_prev;
  41.         // Check if |y - y_center| <= S_prev +1 -x_prime
  42.         ll diff = abs(y - y_center);
  43.         ll limit = S_prev +1 - x_prime;
  44.         if(diff <= limit){
  45.             cout << "0\n";
  46.         }
  47.         else{
  48.             cout << "1\n";
  49.         }
  50.     }
  51. }
  52.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
6
1 1
5 3
8 2
8 6
5 4
6 4
stdout
copy 
1
0
1
0
1
0
https://ideone.com/tfhUjj
language:
C++14 (gcc 8.3)
created:
3 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!