Submission #1168042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168042		SmuggingSpun	XOR (IZhO12_xor)	C++20	0 / 100	2092 ms	17740 KiB

xor

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int lim = 25e4 + 5;
struct Node{
    int child[2];
    Node(){
        this->child[0] = this->child[1] = -1;
    }
};
vector<Node>trie;
void insert_number(int x){
    for(int i = 29, root = 0; i > -1; i--){
        bool nxt = (x >> i & 1);
        if(trie[root].child[nxt] == -1){
            trie[root].child[nxt] = trie.size();
            trie.emplace_back(Node());
        }
        root = trie[root].child[nxt];
    }
}
int get_max(int x){
    int ans = 0;
    for(int i = 29, root = 0; i > -1; i--){
        bool nxt = (x >> i & 1);
        if(trie[root].child[!nxt] != -1){
            ans |= 1 << i;
            nxt = !nxt;
        }
        root = trie[root].child[nxt];
    }
    return ans;
}
int n, X, a[lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n >> X;
    a[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    int low = 1, high = n, p, ans;
    while(low <= high){
        int mid = (low + high) >> 1;
        trie.clear();
        trie.emplace_back(Node());
        bool flag = false;
        for(int i = mid; i <= n; i++){
            insert_number(a[i - mid]);
            if(get_max(a[i]) >= X){
                flag = true;
                p = i;
                break;
            }
        }
        if(flag){
            low = (ans = mid) + 1;
        }
        else{
            high = mid - 1;
        }
    }
    cout << p - ans + 1 << " " << ans;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100