[Codeforces] E. Compatible Numbers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Compatible Numbers
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : SOS DP
Verdict           : Accepted

#include "bits/stdc++.h"  
#include "ext/pb_ds/assoc_container.hpp"  
#include "ext/pb_ds/tree_policy.hpp"  
  
using namespace std;  
using namespace __gnu_pbds;  
  
template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
  
#define ll               long long int  
#define endl             '\n'  
  
static const int maxn = (1 << 22) + 5;  
  
//int dp[(1 << 22) + 5][23];  
int a[maxn];  
int dp[(1 << 22) + 5];  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      vector <int> arr(n);  
      vector <int> brr(n);  
      for (int &x : arr) cin >> x;  
      int N = 22;  
      memset(a, -1, sizeof a);  
      memset(dp, -1, sizeof dp);  
      for (int i = 0; i < n; i++)  
      {  
            int x = arr[i];  
            int mask = 0;  
            for (int i = 0; i < N; i++)  
            {  
                  bool val = (bool)(x & (1 << i));  
                  if (val == 0) mask |= (1 << i);  
                  else mask &= ~(1 << i);  
            }  
            a[x] = x;  
            brr[i] = mask;  
      }  
      /* 
      for (int mask = 0; mask < (1 << N); mask++) 
      { 
            for (int i = 0; i < N; i++) 
            { 
                  if (mask & (1 << i)) 
                  { 
                        if (i == 0) 
                        { 
                              if (a[mask] != -1) dp[mask][i] = a[mask]; 
                              else if (a[mask ^ (1 << i)] != -1) dp[mask][i] = a[mask ^ (1 << i)]; 
                        } 
                        else 
                        { 
                              if (dp[mask][i - 1] != -1) dp[mask][i] = dp[mask][i - 1]; 
                              else if (dp[mask ^ (1 << i)][i - 1] != -1) dp[mask][i] = dp[mask ^ (1 << i)][i - 1]; 
                        } 
                  } 
                  else 
                  { 
                        if (i == 0) 
                        { 
                              if (a[mask] != -1) dp[mask][i] = a[mask]; 
                        } 
                        else 
                        { 
                              if (dp[mask][i - 1] != -1) dp[mask][i] = dp[mask][i - 1]; 
                        } 
                  } 
            } 
      } 
      for (int i = 0; i < n; i++) cout << dp[ brr[i] ][N - 1] << " \n"[i == n - 1]; 
      */  
      for (int mask = 0; mask < (1 << N); mask++) dp[mask] = a[mask];  
      for (int i = 0; i < N; i++)  
      {  
            for (int mask = 0; mask < (1 << N); mask++)  
            {  
                  if (mask & (1 << i) and dp[mask ^ (1 << i)] != -1) dp[mask] = dp[mask ^ (1 << i)];  
            }  
      }  
      for (int i = 0; i < n; i++) cout << dp[ brr[i] ] << " \n"[i == n - 1];  
}