Cod sursa(job #947371)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 7 mai 2013 11:40:21
Problema Xor Max Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<fstream>
#include<vector>

#define left l
#define right r

using namespace std;

class node{
public:

  node(){
    zero = 0;
    one = 0;
  }

  node(int z1, int o1){
    zero = z1;
    one = o1;
  }

  friend void update(int x);
  friend int query(int x);

private:
  int zero, one;
};

vector<node> t;

int p = 0;

void update(int x){
  if(t.empty())
    t.push_back(node());
  int now = 0;
  for(int i = 20; i >= 0; --i)
    if(x & (1 << i)){
      if(t[now].one == 0){
        t[now].one = ++p;
        t.push_back(node());
        now = p;
      }
      else
        now = t[now].one;
    }
    else{
      if(t[now].zero == 0){
        t[now].zero = ++p;
        t.push_back(node());
        now = p;
      }
      else
        now = t[now].zero;
    }
}

int query(int x){
  int now = 0, y = 0;
  for(int i = 20; i >= 0; --i)
    if(x & (1 << i)){
      if(t[now].zero == 0){
        y += 1 << i;
        now = t[now].one;
      }
      else
        now = t[now].zero;
    }
    else{
      if(t[now].one == 0)
        now = t[now].zero;
      else{
        y += 1 << i;
        now = t[now].one;
      }
    }
  return x ^ y;
}

int n, ans, l, r, num[100005], pxor[100005];

void read(){
  ifstream in("xormax.in");

  in >> n;

  for(int i = 1; i <= n; ++i){
    in >> num[i];
    pxor[i] = pxor[i - 1] ^ num[i];
    if(ans < pxor[i]){
      ans = pxor[i];
      left = 1;
      right = i;
    }
  }
}

void solve(){
  int changed = 0;

  for(int i = 1; i <= n; ++i){
    update(pxor[i]);
    int pans = query(pxor[i]);
    if(pans > ans){
      ans = pans;
      changed = i;
    }
  }

  if(changed)
    for(int i = changed - 1; i > 0; --i)
      if((pxor[i] ^ pxor[changed]) == ans){
        left = i + 1;
        right = changed;
        break;
      }
}

void write(){
  ofstream out("xormax.out");

  out << ans << " " << left << " " << right;
}

int main(){
  read();
  solve();
  write();

  return 0;
}