Cod sursa(job #3166036)

Utilizator StefannnnnStefan Stefannnnn Data 7 noiembrie 2023 16:18:36
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;

int sp[100001], cur_left;

struct node {
    node *f[2];
    int in_nr, cuv;
    node() {
        f[1] = f[0] = NULL;
        in_nr = 0, cuv = 0;
    }
};

void update(node *root, int x, int ind) {
    node *curr = root;
    for(int i = 21; i > -1; i --) {
        bool ok = (((1 << i) & x) > 0);
        if(curr->f[ok] == NULL) {
            curr->f[ok] = new node;
        }
        curr = curr->f[ok];
        curr->in_nr ++;
    }
    curr->cuv = ind;
}

int max_xor(node *root, int x) {
    cout << "PENTRU " << x << endl << endl;
    int xor_max = 0;
    node *curr = root;
    for(int i = 21; i > -1; i --) {
        bool ok = (((1 << i) & x) > 0);
    cout << "inv bit " << (1 << i) << " ese ";
        if(ok == 1) {
            ok = 0;
        } else {
            ok = 1;
        }
        cout << ok << endl;
        if(curr->f[ok] != NULL) {
                cout << "il putem lua\n";
            xor_max += (1 << i);
            curr = curr->f[ok];
        } else if(curr->f[(ok == 1 ? ok = 0 : ok = 1)] != NULL) {
            cout << "nu il putem lua\n";
            curr = curr->f[ok];
        }
    }
    cout << endl;

    cur_left = curr->cuv;
    return xor_max;
}

int main() {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    node *root = new node;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        int a;
        cin >> a;
        sp[i] = (sp[i - 1] ^ a);
        update(root, sp[i], i);
    }
    int ans = 0, l, r;
    for(int i = 1; i <= n; i ++) {
        int maxx = max_xor(root, sp[i]);
        maxx = max(maxx, sp[i] ^ sp[i - 1]);
        if(maxx > ans) {
            ans = maxx;
            if(i >= cur_left) {
                l = cur_left + 1;
                r = i;
            } else {
                r = cur_left;
                l = i + 1;
            }
        } else if(ans == maxx) {
            int st = min(i, cur_left) + 1;
            int dr = max(i, cur_left);
            if(dr >= r) {
                dr = r;
                l = st;
            }
        }
    }
    cout << ans << " " << l << " " << r;
    node *curr = root;
    return 0;
}