Submission #1361414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361414		po_rag526	XOR (IZhO12_xor)	C++20	100 / 100	109 ms	56508 KiB

xor

/*==============================================*/
//!  Captain_Luffy_
/*==============================================*/
#include <bits/stdc++.h>
#define ll long long
#define el '\n'
#define all(v) v.begin() , v.end()
#define allr(v) v.rbegin() , v.rend()
#define YES cout << "YES" << el ;
#define no cout << "NO" << el ;
const ll N = 2e5 + 5 , M = 1e3 + 5 , mod = 1e9 + 7 , mod2 = 998244353 , INF = 1e18 , OO = 0x3f3f3f3f ;
#define RAMY ios_base::sync_with_stdio(0) , cout.tie(0) , cin.tie(0) ;
using namespace std ;
/*==============================================*/
//! Look Down :)
/*==============================================*/

struct Binary_trie
{
    int mx = 30 ;
    struct Node
    {
        Node * ch[2] ;
        int mn_l ;
        Node()
        {
            ch[0] = ch[1] = 0 ;
            mn_l = INT_MAX ;
        }
    };
    
    Node * root = new Node() ;

    void insert ( int x , int l )
    {
        Node * cur = root ;
        cur -> mn_l = min ( cur -> mn_l , l ) ;

        for ( int i = mx ; i >= 0 ; i -- )
        {
            bool idx = ( x >> i ) & 1 ;
            if ( cur -> ch[idx] == 0 )
            {
                cur -> ch[idx] = new Node() ;
            }

            cur = cur -> ch[idx] ;
            cur -> mn_l = min ( cur -> mn_l , l ) ;   
        }
    }

    int query ( int x , int k )
    {
        Node * cur = root ;
        int ret = 1e9 ;
        bool f = 0 ;

        for ( int i = mx ; i >= 0 ; i -- )
        {
            if ( !cur ) break ; 
            bool x_bit = ( x >> i ) & 1 ;
            bool k_bit = ( k >> i ) & 1 ;

            if (f) 
            {
                ret = min ( ret , cur -> mn_l ) ;
                break ;
            }

            if ( k_bit )
            {
                cur = cur -> ch[x_bit^1] ;
            }
            else
            {
                if ( cur -> ch[x_bit^1] ) 
                ret = min ( ret , cur -> ch[x_bit^1] -> mn_l ) ;

                cur = cur -> ch[x_bit] ;
            }
        }

        if ( cur ) ret = min ( cur -> mn_l , ret ) ;
        return ret ;
    }
};

/*==============================================*/
void Captain()
{
    ll n , x ;
    cin >> n >> x ;

    
    Binary_trie tr ;
    tr.insert(0 , 0) ;

    ll len = 0 , l = 0 , X = 0 ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        ll a ; cin >> a ; 
        
        X ^= a ;
        
        ll L = tr.query( X , x ) ;
        
        if ( i - L > len && L != INT_MAX ) 
        {
            len = i - L ;
            l = L + 1 ;
        }
        
        tr.insert( X , i ) ;

    }

    cout << l << ' ' << len << el ;
    
}
/*==============================================*/
void pre()
{
    
}
/*==============================================*/
int main()
{
    RAMY
    ll test = 1 ;
    if ( fopen("input.txt","r") )
    {
        freopen("input.txt","r",stdin) ;
        freopen("output.txt","w",stdout) ;
    }
    // cin >> test ;
    pre() ;
 
    for ( int te = 1 ; te <= test ; te ++ )
    { 
        // cout << "Case " << te << ":" << el ;
        Captain() ; 
    }
 
    return 0 ;
}
/*==============================================*/
//? ??????????????????????????????????????????????
//? ????????????????????????????????????????????????
//? ???????????????????????????????????????????????????
//? ??????????????  ????????????????????????????????????
//? ????????????????????????????????6?????????????????????
//? ??????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????????
//? ???????????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????????????
//? ???????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????
//? ????? ??????????????????????????????????????????????????????
//? ????? ??????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????
//? ???????????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????
//? ???????????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????
//? ??????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????????
//? ???????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????????????
//? ??????????????????????????????????????????????????????????????
//? ????????????????????????????????????????????????????????????????
//? ?????????????????????????????????????????????????????????????????

Compilation message (stderr)

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

• Subtask 1: 100 / 100