제출 #1138569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138569		dr.rabi3	XOR (IZhO12_xor)	C++20	0 / 100	230 ms	327680 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;

template<typename T , class CMP = function<T( const T& , const T& )>>
class SparseTable {
  public:
  int n , max_log;
  vector<vector<T>> sp;
  CMP func;

  SparseTable( const vector<T>& a , const CMP& f ) : func( f ) {
    n = a.size( );
    max_log = 32 - __builtin_clz( n );
    sp.resize( max_log );
    sp [ 0 ] = a;
    for ( int j = 1; j < max_log; ++j ) {
      sp [ j ].resize( n - ( 1 << j ) + 1 );
      for ( int i = 0; i + ( 1 << j ) <= n; ++i ) {
        sp [ j ][ i ] = func(
            sp [ j - 1 ][ i ] ,
            sp [ j - 1 ][ i + ( 1 << ( j - 1 ) ) ]
        );
        }
      }
    }

  T query( int l , int r ) {
    T ans = 0;
    for ( int p = max_log - 1; p >= 0; p-- ) {
      if ( ( 1 << p ) <= r - l + 1 ) {
        ans = func( ans , sp [ p ][ l ] );
        l += ( 1 << p );
        }
      }
    return ans;
    }

  T get( int l , int r ) const {
    int lg = __lg( r - l + 1 );
    return func(
        sp [ lg ][ l ] ,
        sp [ lg ][ r - ( 1 << lg ) + 1 ]
    );
    }
  };
void doWork( int TC ) {
  int n , x;
  cin >> n >> x;
  vector<int>v( n );
  for ( auto& i : v ) cin >> i;
  SparseTable<int> spXOR( v , [ & ] ( int a , int b ) {return a ^ b; } );

  auto can = [ & ] ( int md ) -> bool {
    for ( int i = 0; i <= n - md; i++ ) {
      if ( spXOR.query( i , i + md - 1 ) >= x )
        return 1;
      }
    return 0;
    };

  int lo = 0 , hi = n , ans = 0;
  while ( lo <= hi ) {
    int md = ( lo + hi ) >> 1;
    if ( can( md ) ) lo = md + 1 , ans = md;
    else hi = md - 1;
    }
  for ( int i = 0; i <= n - ans; i++ ) {
    if ( spXOR.query( i , i + ans - 1 ) >= x )
      return void( cout << i + 1 << ' ' << ans );
    }
  }

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

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 100