yes, it will be in English.

Yes

just checking i and i + 1 works too

Yeah,the editorial is overcomplicated,there is an easy brute:

# include <bits/stdc++.h>
using namespace std;
int main(void)
{
    srand(time(0));
    int n;
    static int s[1 << 20];
    fi>>n;
    for (int i = 1;i <= n;++i)
        fi>>s[i];
    sort(s + 1,s + 1 + n);
    ll ans = 0;
    for (int i = 1;i <= n;++i)
    {
        int l = i + 1;
        int r = min(n,i + 100);
        for (int j = l;j <= r;++j)
            ans = max(ans,1ll * (s[i] & s[j]) * (s[i] | s[j]));
        l = max(i + 1,n - 100);
        r = n;
        for (int j = l;j <= r;++j)
            ans = max(ans,1ll * (s[i] & s[j]) * (s[i] | s[j]));
    }
    while (clock() / CLOCKS_PER_SEC <= 0.98)
    {
        int l = rand() % n + 1;
        int r = rand() % n + 1;
        if (l != r)
            ans = max(ans,1ll * (s[l] & s[r]) * (s[l] | s[r]));
    }
    fo << ans << '\n';
    return 0;
}

the solution with just two maximal numbers gets 100%, that's fine.

By the editorial we can prove that we only need to consider the top log(a_i) number。 We didn't find it before contest. I'm very sorry.

My solution :

cin>>n;
    cin>>arr[1];
    mx = arr[1];

    for(int i=2; i<=n; i++){
        cin>>arr[i];
        ans = max(ans, ll((arr[i]&mx)*(arr[i]|mx)));
        mx = max(mx, arr[i]);
    }

    cout<<ans<<endl;

For the j-th bit and for set S,you partition numbers in 2 sets. S0-those who have j-th bit set to 0, S1-those who have j-th bit set to 1. Let's call the answer for j-th bit and set S f(S,j).

Now we got three cases:

• If cardinal of any of them is 0, our answer will surely take only numbers from one set. So there is no need to make the choice now, we will make it later and apply same algorithm for (j-1)-th bit. So we call f(S,j-1).

• |S1| = 1 and the rest are in S0. Now the answer could be in S0 or the x in S1 and some number in S0. Let's brute-force through all y in S0, relax the answer with (x&y)*(x|y), then call f(S0,j-1).

• |S1| > 1. This needs some observation. It's better from now on to choose only numbers from S1. Why? Because choosing 2 numbers with j-th bit 1 would make the answer have the 2*j-th bit 1 at least, which is the best and cannot be done with other 2 numbers in S. So we will make the choice later and call f(S1, j-1).

You can see that we actually relax the answer in step2, but it's not necessarily to go there for some input(ex. all numbers are equal). You got to be careful. Also 2nd step is done at most log times. When I say we make the choice later, it's something like f(S,j) = F(S',j-1).

For a better intuition of why it works, it's like excluding at every step some numbers we surely know it won't give the best answer,if that's the case. The key was to make the observation at 3rd step.