SOS DP, C++ (gcc) - rextester

SOS DP

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>

const int N = 1 << 22;

int dp[2][N];

int solve(){
    int prv = 0, cur = 1;
    for(int j = 0; j < 22; j++){
        for(int i = 0; i < N; i++){
            if(i & (1 << j))
                dp[cur][i] = dp[prv][i ^ (1 << j)];
            else{
                if(dp[prv][i] != -1) dp[cur][i] = dp[prv][i];
                else dp[cur][i] = dp[prv][i ^ (1 << j)];
            }
        }
        prv ^= 1;
        cur ^= 1;
    }
    return prv;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for(int j = 0; j < n; j++) cin >> a[j];
    for(int j = 0; j < N; j++) dp[0][j] = -1;
    for(int j = 0; j < n; j++) if(dp[0][a[j]] == -1) dp[0][a[j]] = j;
        
    int ind = solve();
    for(int j = 0; j < n; j++)
        if(dp[ind][a[j]] == -1) cout << -1 << " ";
        else cout << a[dp[ind][a[j]]] << " ";
    cout << endl;
    return 0;
}


run \| edit \| history \| help	0