Cod sursa(job #1054645)

Utilizator bolovMihail Balan bolov Data 14 decembrie 2013 00:35:14
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 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<int> xor_table(seq.size());
  int xor_res = 0;
  auto xor_it = xor_table.begin();
  auto seq_it = seq.begin();
  while (seq_it < seq.end()) {
    xor_res ^= *seq_it;
    *xor_it = xor_res;

    ++xor_it;
    ++seq_it;
  }

  int max = 0, start, stop;

  for (int j = 1; j < (int) seq.size(); ++j) {
    for (int i = j - 1; i > 0; --i) {
      int xor_res = (i == 0) ? xor_table[j] : (xor_table[i - 1] ^ xor_table[j]);
      
      if (xor_res > max) {
        max = xor_res;
        start = i;
        stop = j;

      }

    }
  }
  

  /*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;
}