fork(1) download
  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
stdin
5
5 2 1 4 3
stdout
7