Submission #1287331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287331		quan606303	XOR (IZhO12_xor)	C++20	100 / 100	116 ms	58528 KiB

xor

/*
 * @Author: RMQuan 
 * @Date: 2025-11-04 10:11:19 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-11-04 14:17:38
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=3e5+7;
const int inf=1e18; 
const int LOG=30;
int n,a[maxn],pre_xor[maxn];
int k;
struct trie_node
{
    trie_node *child[2];
    int mn_idx;
    trie_node()
    {
        child[0]=child[1]=NULL;
        mn_idx=inf;
    }
};
struct trie
{
    trie_node *root;
    trie(int cnt)
    {
        root=new trie_node;
    }
    void add(int val,int idx)
    {
        trie_node *p=root;
        for (int i=LOG;i>=0;i--)
        {
            bool index=val&(1<<i);
            if (p->child[index]==NULL)p->child[index]=new trie_node();
            p=p->child[index];
            p->mn_idx=min(p->mn_idx,idx);
        }
    }
    int get(int val)
    {
        trie_node *p=root;
        int ans=inf;
        for (int i=LOG;i>=0;i--)
        {
            bool index_k=k&(1<<i);
            bool index_val=val&(1<<i);
            if (index_k==0)
            {
                //case 1 : dung o day
                bool need_index=1^index_val;
                if (p->child[need_index]!=NULL)ans=min(ans,p->child[need_index]->mn_idx);
                //case 2 : di tiep
                need_index=0^index_val;
                if (p->child[need_index]!=NULL)p=p->child[need_index];
                else return ans;
            }
            else if (index_k==1)
            {
                bool need_index=1^index_val;
                if (p->child[need_index]!=NULL)p=p->child[need_index];
                else return ans;
            }
        }
        return min(ans,p->mn_idx);
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>k;
    int ans1=-inf,ans2=inf;
    trie st(0);
    st.add(0,0);
    int sum=0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum=sum^a[i];
        int tam=st.get(sum);
        if (tam>=inf)
        {
            st.add(sum,i);
            continue;
        }
        int cur_len=i-tam;
        int pos=i-tam+1;
        if (cur_len>ans1)
        {
            ans1=cur_len;
            ans2=i;
        }
        else if (cur_len==ans1)ans2=min(ans2,i);
        st.add(sum,i);
    }
    cout<<ans2-ans1+1<<" "<<ans1<<endl;
   
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int32_t main()':
xor.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xor.cpp:94:5: note: in expansion of macro 'file'
   94 |     file();
      |     ^~~~
xor.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:94:5: note: in expansion of macro 'file'
   94 |     file();
      |     ^~~~

• Subtask 1: 100 / 100