Submission #1139786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139786		dr.rabi3	XOR (IZhO12_xor)	C++20	0 / 100	396 ms	286456 KiB

xor

// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define ed '\n'
using namespace std;


struct node {
  int ch [ 2 ] { -1, -1 } , sz = 0;
  vector<int>frq [ 2 ];
  int& operator[]( int x ) {
    return ch [ x ];
    }
  };

struct BT {
  static const int M = 4;
  vector<node> nodes;

  int newNode( ) {
    return nodes.emplace_back( ) , nodes.size( ) - 1;
    }

  void init( ) { nodes.clear( ) , newNode( ); }

  BT( ) { init( ); }

  /// +1 to add, -1 to delete
  void update( int val , int idx ) {
    int u = 0 , v;
    for ( int i = M - 1; i >= 0; --i ) {
      v = val >> i & 1;
      if ( !~nodes [ u ][ v ] ) {
        int ch = newNode( );
        nodes [ u ][ v ] = ch;
        }
      nodes [ u ].frq [ v ].push_back( idx );
      nodes [ u ].sz++;
      u = nodes [ u ][ v ];
      }
    nodes [ u ].frq [ v ].push_back( idx );
    nodes [ u ].sz++;
    }

  /// Count the number of integers such that a[i] XOR num >= l
  int query( int num , int l ) {
    int u = 0 , ans = 1e9;
    for ( int i = M - 1; i >= 0; i-- ) {
      int btP = num >> i & 1;
      int btL = l >> i & 1;
      if ( btL ) {
        u = nodes [ u ][ !btP ];
        }
      else {
        if ( !nodes [ u ].frq [ !btP ].empty( ) )
          ans = min( ans , nodes [ u ].frq [ !btP ].front( ) );
        u = nodes [ u ][ btP ];
        }
      if ( u == -1 )return ans;
      }
    for ( int i : {0 , 1} )
      if ( !nodes [ u ].frq [ i ].empty( ) )
        ans = min( ans , nodes [ u ].frq [ i ].front( ) );

    return ans;
    }
  };

void doWork( int TC ) {
  int n , x; cin >> n >> x;
  vector<int>v( n + 1 );
  for ( int i = 1; i <= n; i++ ) cin >> v [ i ];
  BT trie;
  int _xor = 0;
  pair<int , int>ans;
  for ( int i = 1; i <= n; i++ ) {
    trie.update( _xor , i );
    _xor ^= v [ i ];
    int idx = trie.query( _xor , x );
    if ( idx < 1e9 ) {
      if ( i - idx + 1 > ans.second ) ans = { idx, i - idx + 1 };
      }
    }
  cout << ans.first << " " << ans.second;
  }

int32_t main( ) {
  ios_base::sync_with_stdio( false );
  cout.tie( nullptr );
  cin.tie( nullptr );
#ifndef ONLINE_JUDGE
  freopen( "input.txt" , "r" , stdin );
  freopen( "output.txt" , "w" , stdout );
#else
  // freopen("banana.in", "r", stdin);
  // freopen("gcd.out", "w", stdout);
#endif
  int _ = 1;
  // cin >> _;
  for ( int __ = 1; __ <= _; __++ ) {
    // cout << "Case " << __ << ":\n";
    doWork( __ );
    if ( __ < _ ) cout << '\n';
    // cout << '\n';
    }
  return 0;
  }

Compilation message (stderr)

xor.cpp: In function 'int32_t main()':
xor.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen( "input.txt" , "r" , stdin );
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   freopen( "output.txt" , "w" , stdout );
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100