Cod sursa(job #2823151)

Utilizator andreic06Andrei Calota andreic06 Data 27 decembrie 2021 12:17:53
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <fstream>

using namespace std;
const int ROOT = 0;
const int NMAX = 1e5;
const int SIGMA = 2;
const int MAX_DEPTH = 21;

int bit_array[MAX_DEPTH];
int second_bit_array[MAX_DEPTH];

void get_bit ( int x ) {
    for ( int index = MAX_DEPTH - 1; index; index -- ) {
       bit_array[index] = x % 2;
       x /= 2;
    }
}
int get_number ( int bit[] ) {
    int result = 0;
    for ( int index = 0; index < MAX_DEPTH; index ++ )
       result = result * 2 + bit[index];
    return result;
}
void delete_array ( int bit[] ) {
    for ( int i = 0; i < MAX_DEPTH; i ++ )
       bit[i] = 0;
}

void debug_array ( int bit[] ) {
    for ( int i = 0; i < MAX_DEPTH; i ++ )
       cout << bit[i] << " ";
    cout << "\n";
}

struct BIT_TRIE {
      struct node {
            int link[SIGMA];
            int end_prefix;
      } ds[1 + NMAX * MAX_DEPTH];

      int index = 0;
      void add_number ( int bit[], int pos ) {
          int node = ROOT;
          for ( int i = 0; i < MAX_DEPTH; i ++ ) {
             if ( !ds[node].link[bit[i]] )
               ds[node].link[bit[i]] = ++ index;
             node = ds[node].link[bit[i]];
          }
          ds[node].end_prefix = pos;
      }

      int search_invers ( int bit[], int result[] ) {
          int node = ROOT;
          for ( int i = 0; i < MAX_DEPTH; i ++ ) {
             if ( ds[node].link[1 - bit[i]] ) {
               result[i] = 1 - bit[i];
               node = ds[node].link[1 - bit[i]];
             }
             else {
               result[i] = bit[i];
               node = ds[node].link[bit[i]];
             }
          }
          return ds[node].end_prefix;
      }
} trie;
ifstream fin ( "xormax.in" );
ofstream fout ( "xormax.out" );
int main()
{
   int pref_xor = 0, max_xor = 0;
   int b = 1, e = 1;

   int n; fin >> n;
   for ( int i = 1; i <= n; i ++ ) {
      get_bit ( pref_xor );
      trie.add_number ( bit_array, i );
      int x; fin >> x; pref_xor ^= x;
      get_bit ( pref_xor ); delete_array ( second_bit_array );

      ///debug_array ( bit_array );
      ///debug_array ( second_bit_array );

      int pos = trie.search_invers ( bit_array, second_bit_array );
      ///debug_array ( second_bit_array );

      int best = get_number ( second_bit_array );
      ///cout << best;
      best = pref_xor ^ best;
      if ( best > max_xor ) {
        max_xor = best;
        b = pos, e = i;
      }
   }
   fout << max_xor << " ";
   fout << b << " " << e;

    return 0;
}