fork(1) download
copy 
  1. //IO
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <fstream>
  5. #include <sstream>
  6. //container
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <string>
  14. //other
  15. #include <algorithm>
  16. #include <math.h>
  17. #include <time.h>
  18. #include <functional>
  19.  
  20. using namespace std;
  21.  
  22. // ifstream fin ("data.in");
  23. // ofstream fout ("data.out");
  24.  
  25. int main(int argc, char *argv[])
  26. {
  27.  int n;
  28.  cin >> n;
  29.  vector<int> a;
  30.  vector<pair<int, int> > sorted_a;
  31.  a.resize(n);
  32.  sorted_a.resize(n);
  33.  for (int i = 0; i < n; ++i)
  34.   {
  35.    cin >> a[i];
  36.    sorted_a[i] = make_pair(a[i], i);
  37.   }
  38.  sort(sorted_a.begin(), sorted_a.end());
  39.  int max_sc = a[0] ^ a[1];
  40.  vector<int> from_right;
  41.  vector<int> from_left;
  42.  from_left.resize(n, -1);
  43.  from_right.resize(n, -1);
  44.  int real_i;
  45.  int startr, startl;
  46.  for (int i = 0; i < n; ++i)
  47.   {
  48.    // take next smallest number position
  49.    real_i = sorted_a[i].second;
  50.    // To find a number it can be xor'ed with, we need to find next
  51.    // number bigger than ours.
  52.    // To find next bigger number from right for this smallest number,
  53.    // we need to go right from the position(or it's from_right
  54.    // position) of latest visitor from the right. This value is stored
  55.    // in from_right.
  56.    // That's because if someone visited us from there, then everybody
  57.    // on it's way is smaller then our number.
  58.    // If noone visited us, just go one point right from current
  59.    // position
  60.    startr = (from_right[real_i]==-1)?real_i+1:from_right[real_i]+1;
  61.    if(startr < n)
  62.     {
  63.      // We go right, so we wisited from left
  64.      // If someone visited us from left, put that number.
  65.      // from_left[real_i] will never change from this point, since we
  66.      // will be smaller than everyone after us.
  67.      from_left[startr] = (from_left[real_i]==-1)?real_i:from_left[real_i];
  68.      if((a[real_i]^a[startr]) > max_sc)
  69.       max_sc = a[real_i]^a[startr];
  70.     }
  71.    // same for other side
  72.    startl = (from_left[real_i]==-1)?real_i-1:from_left[real_i]-1;
  73.    if(startl >= 0)
  74.     {
  75.      from_right[startl] = (from_right[real_i]==-1)?real_i:from_right[real_i];
  76.      if((a[real_i]^a[startl]) > max_sc)
  77.       max_sc = a[real_i]^a[startl];
  78.     }
  79.   }
  80.  cout << max_sc << endl;
  81.  return 0;
  82. }
  83.  
Success #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
5
5 2 1 4 3
stdout
copy 
7
https://ideone.com/vix2hL
language:
C++ (gcc 8.3)
created:
11 years 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!