1 solutions

  • 0
    @ 2025-6-17 21:21:41
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    char buf[1<<20],*p1,*p2;
    int a[1000000];
    inline char gc()  // 快速读字符
    {
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==buf?EOF:*p1++;
    }
    inline void read(int &x)  // 快读
    {
        int c;
        while((c=gc())<'0'||c>'9');
        for(x=c^48;(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48));
    }
    int main()
    {
    	int n,st,ed;
    	read(n);
        st=0,ed=n-1;  // 当前寻找最优解的范围
    	for(int i=0;i<n;++i)
        {
            read(a[i]);
        }
        sort(a,a+n);
        for(int bit=1<<30;bit;bit>>=1)  // 从高到低按位枚举,bit标识当前位
        {
            if((a[st]&bit)||!(a[ed]&bit))  // 这位上全部相同,跳过
            {                              // 即最小的数这位为1,或最大的数这位为0
                continue;
            }
            if((a[ed]&bit)&&!(a[ed-1]&bit))  // 只有最后一个数这位为1
            {
                int t=a[ed]^=bit,i;
                for(i=ed-1;i>=st&&a[i]>t;--i)  // 单轮插入排序
                {
                    a[i+1]=a[i];
                }
                a[i+1]=t;
            }
            else
            {
                int l=st,r=ed,mid;
                while(l<r)  // 二分0段和1段的分界点,找到第一个这位为1的数
                {
                    mid=(l+r)>>1;
                    if(a[mid]&bit) r=mid;
                    else l=mid+1;
                }
                st=l;  // 缩小范围
            }
            if(ed-st<=1)  // 范围缩小到2个数以内,找到答案
            {
                break;
            }
        }
        printf("%d",a[st]&a[ed]);
    	return 0;
    }
    
    • 1

    Information

    ID
    132
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    2
    Accepted
    2
    Uploaded By