Cod sursa(job #3167030)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 9 noiembrie 2023 22:00:14
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct Node
{
    int prefpos;
    int muchii[2];
};

int v[100001];
int prefxor[100001];

Node trie[2200000];
int sz,currpos;

void ins(string s)
{
    int node;
    int j;
    node=0;
    for (j=0; j<s.size(); j++)
    {
        if (trie[node].muchii[s[j]-'0']==0)
        {
            sz++;
            trie[sz]= {0,0};
            trie[node].muchii[s[j]-'0']=sz;
        }
        node=trie[node].muchii[s[j]-'0'];
    }
    trie[node].prefpos=max(currpos,trie[node].prefpos);
}

int bestnode;

string best(string s)
{
    int j;
    int node;
    int secondnode;
    node=0;
    secondnode=0;
    string res;
    for (j=0; j<s.size(); j++)
    {
        if (s[j]=='1')
        {
            node=trie[node].muchii[1];
            if (trie[secondnode].muchii[0]==0)
            {
                secondnode=trie[secondnode].muchii[1];
                res+="1";
            }
            else
            {
                secondnode=trie[secondnode].muchii[0];
                res+="0";
            }
        }
        else
        {
            node=trie[node].muchii[0];
            if (trie[secondnode].muchii[1]==0)
            {
                secondnode=trie[secondnode].muchii[0];
                res+="0";
            }
            else
            {
                secondnode=trie[secondnode].muchii[1];
                res+="1";
            }
        }
    }
    bestnode=secondnode;
    return res;
}

int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,i,j,mx,ans,maxl,l,r;
    string s,s2;
    fin >> n;
    for (j=1; j<=n; j++)
    {
        fin >> v[j];
        prefxor[j]=prefxor[j-1]^v[j];
    }
    trie[0]= {0,0};
    sz=0;
    mx=0;
    for (j=1; j<=n; j++)
    {
        currpos=j;
        s="";
        for (i=21; i>=0; i--)
        {
            if (prefxor[j]&(1<<i))
                s+="1";
            else
                s+="0";
        }
        ins(s);
        bestnode=0;
        s2=best(s);
        maxl=trie[bestnode].prefpos+1;
        reverse(s.begin(),s.end());
        reverse(s2.begin(),s2.end());
        ans=0;
        for (i=0; i<=21; i++)
        {
            if (s[i]!=s2[i])
                ans+=(1<<i);
        }
        if (ans>=mx)
        {
            if (ans==mx)
            {
                if (j<r)
                {
                    mx=ans;
                    r=j;
                    l=maxl;
                }
                else if (j==r && maxl>l)
                {
                    mx=ans;
                    r=j;
                    l=maxl;
                }
            }
            else
            {
                mx=ans;
                r=j;
                l=maxl;
            }
        }
    }
    fout << mx << " " << l << " " << r;
}