Submission #1149222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149222		hoksha	XOR (IZhO12_xor)	C++20	0 / 100	877 ms	24384 KiB

xor

#include "bits/stdc++.h"
using namespace std;
const int M = 31;
struct Node{
   int ch[2]{};
   int sz = 0;
   int mnIndex = 1e9;
   int isEnd = 0;
   int &operator[](char x){
       return ch[x];
   }
};
struct Trie{
    vector<Node>trie;

    int newNode(){
        trie.emplace_back();
        return trie.size() - 1;
    }
    Trie(){init();}
    void init() {
        trie.clear();
        trie.emplace_back();
    }
    void insert(int num, int index){
        int cur = 0;
        for(int i = M;  i>= 0; i--){
            int bit = num >>i & 1;
            if (trie[cur][bit] == 0) trie[cur][bit] = newNode();
            cur = trie[cur][bit];
            trie[cur].mnIndex = min(trie[cur].mnIndex,index);
        }
        trie[cur].isEnd++;
    }

    int getAns(int pre, int x){
        int cur = 0;
        int minAns = 1e9;
        for(int i = M; i >= 0; --i){
            int bitP = pre >> i & 1;
            int bitX = x >> i & 1;
            if (bitP == 1 && bitX == 0){
                if (trie[cur][0]){
                    minAns = min(minAns, trie[trie[cur][0]].mnIndex);
                }
            }
            else if (bitP == 0 && bitX == 0){
                if (trie[cur][1]){
                    minAns = min(minAns, trie[trie[cur][1]].mnIndex);
                }
            }


            if (trie[cur][bitP ^ bitX]){
                cur = trie[cur][bitP ^ bitX];
            }
            else break;
        }
        if(trie[cur].isEnd){
            minAns = min(minAns, trie[cur].mnIndex);
        }
        return minAns;
    }


};
void fast() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int main(){
   fast();
   int n, x; cin >> n >> x;
   vector<int>a(n + 1);
   for(int i = 1; i <= n; ++i){
       cin >> a[i];
       a[i] ^= a[i - 1];
   }
   Trie trie;
   trie.insert(0, 0);
   int mxL = 0, L = 1e9;
   for(int i = 1; i <= n; i++){
       int minI  = trie.getAns(a[i], x);
       if (minI== 1e9){
           continue;
       }
       if (i  - minI > mxL){
           mxL = i - minI;
           L = minI + 1;
       }
       else if (i - minI == mxL){
           if (minI + 1< L){
               L = minI + 1;
           }
       }
       trie.insert(a[i], i);
   }
   cout << L << ' ' << mxL << endl;





    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100