fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1000006;
  5. const int MAX_BITS = 21;
  6.  
  7. int n, a[MAX_N], ans, bits;
  8. pair<int, int> dp[1 << MAX_BITS];
  9.  
  10. void add(int mask, int w) {
  11.     if (dp[mask].first == -1) {
  12.         dp[mask].first = w;
  13.     } else if (dp[mask].second == -1) {
  14.         if (dp[mask].first == w) return;
  15.         dp[mask].second = w;
  16.         if (dp[mask].first > dp[mask].second) {
  17.             swap(dp[mask].first, dp[mask].second);
  18.         }
  19.     } else {
  20.         if (dp[mask].second < w) {
  21.             dp[mask].first = dp[mask].second;
  22.             dp[mask].second = w;
  23.         } else if (dp[mask].first < w && dp[mask].second != w) {
  24.             dp[mask].first = w;
  25.         }
  26.     }
  27. }
  28.  
  29. void merge(int m1, int m2) {
  30.     if (dp[m2].first != -1) add(m1, dp[m2].first);
  31.     if (dp[m2].second != -1) add(m1, dp[m2].second);
  32. }
  33.  
  34. void solve() {
  35.     memset(dp, -1, sizeof dp);
  36.     cin >> n;
  37.     for (int i = 0; i < n; i++) {
  38.         cin >> a[i];
  39.         add(a[i], i);
  40.         bits = max((int)log2(a[i]), bits);
  41.     }
  42.     bits++;
  43.  
  44.     for (int i = 0; i < bits; i++) {
  45.         for (int mask = 0; mask < (1 << bits); mask++) {
  46.             if (mask & (1 << i)) {
  47.                 merge(mask ^ (1 << i), mask);
  48.             }
  49.         }
  50.     }
  51.  
  52.     for (int i = 0; i < n; i++) {
  53.         int cur = (1 << bits) - 1 - a[i];
  54.         int opt = 0;
  55.         for (int j = bits - 1; j >= 0; j--) {
  56.             if ((cur >> j) & 1) {
  57.                 if (dp[opt ^ (1 << j)].second != -1 && dp[opt ^ (1 << j)].first > i) {
  58.                     opt ^= (1 << j);
  59.                 }
  60.             }
  61.         }
  62.         if (dp[opt].second != -1 && dp[opt].first > i) {
  63.             ans = max(ans, a[i] | opt);
  64.         }
  65.     }
  66.  
  67.     cout << ans << endl;
  68. }
  69.  
  70. int main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.  
  75.     int t = 1;
  76.     // cin >> t;
  77.     while (t--) {
  78.         solve();
  79.     }
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 21420KB
comments (?)
stdin
copy 
4
2 8 4 7
stdout
copy 
12
https://ideone.com/6Nviun
language:
C++14 (gcc 8.3)
created:
1 day 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!