1 solutions
-
0
#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