Cod sursa(job #3121006)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 10 aprilie 2023 10:52:04
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
///Buzatu Giulian
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int NMAX=100005;
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(string& ans,int n)
{
    ans="";
    if(n==0)
        ans.push_back('0');
    while(n>0)
    {
        ans.push_back((n%2)+'0');
        n/=2;
    }
    while(ans.size()<21) /// in case the number doesn't have 20 bits in his binary representation,
        ans.push_back('0');/// we want to extend it, in order to make an accurate search on the trie
    reverse(ans.begin(),ans.end());
}
int main()
{
    f>>n;
    start=stop=1;
    string w;
    makeString(w,partialxor);
    trie=add(trie,w.c_str(),0);
    for(int i=1; i<=n; i++)
    {
        f>>x;
        partialxor=partialxor^x;
        makeString(w,partialxor);
        curr_ans=search_opp(trie,w.c_str());
        if(curr_ans>maxx)
        {
            maxx=curr_ans;
            start=curr_pos+1;///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.c_str(),i);
    }
    g<<maxx<<' '<<start<<' '<<stop;
    ///delete trie;
    return 0;
}