Cod sursa(job #1054599)

Utilizator bolovMihail Balan bolov Data 13 decembrie 2013 23:28:45
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using std::cout;
using std::endl;

template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  if (v.empty()) {
    os << "[empty vector]";
    return os;
  }

  os << "{";

  for (auto it = v.begin(); it < v.end() - 1; ++it) {
    os << *it << ", ";
  }
  os << v.back() << "}";
  return os;
}

int main() {
  std::vector<int> seq;
  std::ifstream ifs;

  ifs.open("xormax.in");
  int n;

  ifs >> n;
  seq.resize(n);

  for (auto &elem : seq) {
    ifs >> elem;
  }
  ifs.close();
  
  //cout << seq << endl;

  std::vector<std::vector<int>> xor_table(seq.size());
  int size = seq.size();
  for (auto &xor_line : xor_table) {
    xor_line = std::vector<int>(size--);
  }
  
  int max = 0, start, stop;
  int i, j;
  
  i = 0;
  auto xor_i = xor_table.begin();
  auto seq_i = seq.begin();
  while(xor_i < xor_table.end()) {

    j = i;
    auto xor_j = xor_i->begin();
    auto seq_j = seq_i;


    int xor_res = 0;
    while (xor_j < xor_i->end()) {
      xor_res ^= *seq_j;
      *xor_j = xor_res;

      if (xor_res > max || (xor_res == max && (j < stop || (j == stop && i > start)))) {
        max = xor_res;
        start = i;
        stop = j;
      }

      ++j;
      ++xor_j;
      ++seq_j;
    }
    
    ++i;
    ++xor_i;
    ++seq_i;
  }


  

  //cout << xor_table << endl;

  //cout << max << " " << start + 1 << " " << stop + 1 << endl;

  std::ofstream ofs;

  ofs.open("xormax.out");
  ofs << max << " " << start + 1 << " " << stop + 1 << endl;
  ofs.close();
  return 0;
}