Cod sursa(job #3121003)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 10 aprilie 2023 10:44:18
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
///Buzatu Giulian
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,x,maxx,start,stop,partialxor,curr_pos,curr_ans;
struct Node
{
    int index;///the index represents the end of the prefix
    vector<Node*>sons;
    Node():sons(2,nullptr) {}
    ~Node()
    {
        for(int i=0; i<2; i++)
            if(this->sons[i]!=nullptr)
                delete this->sons[i];
    }
};
Node* trie=nullptr;
Node* add(Node* p,const char* w,int pos)
{
    if(p==nullptr)
        p=new Node;
    if(w[0]=='\0')
        p->index=pos;
    else
        p->sons[w[0]-'0']=add(p->sons[w[0]-'0'],w+1,pos);
    return p;
}
int search_opp(Node* p,const char* w,int bit=20)///search opposite
{
    if(w[0]=='\0')
    {
        curr_pos=p->index;
        return 0;
    }
    ///we want to take, when possible, the opposite bit to the one from w[0]
    if(p->sons[1-(w[0]-'0')]!=nullptr)
        return (1<<bit)+search_opp(p->sons[1-(w[0]-'0')],w+1,bit-1);
    return search_opp(p->sons[w[0]-'0'],w+1,bit-1);
}
void makeString(char* ans,int n)
{
    int index=20;
    if(n==0)
        ans[index--]='0';
    while(n>0)
    {
        ans[index--]=(n%2)+'0';
        n/=2;
    }
    while(index>=0) /// in case the number doesn't have 20 bits in his binary representation,
        ans[index--]='0';/// we want to extend it, in order to make an accurate search on the trie
}
int main()
{
    f>>n;
    start=stop=1;
    char w[25];
    w[21]='\0';
    makeString(w,partialxor);
    trie=add(trie,w,0);
    for(int i=1; i<=n; i++)
    {
        f>>x;
        partialxor^=x;
        makeString(w,partialxor);
        curr_ans=search_opp(trie,w);
        if(curr_ans>maxx)
        {
            maxx=curr_ans;
            start=curr_pos;///because in order to calculate the xor fr [i...j] we use i-1 and that is the index returned by the function
            stop=i;
        }
        trie=add(trie,w,i);
    }
    g<<maxx<<' '<<start+1<<' '<<stop;
    delete trie;
    return 0;
}