QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196628 | #6522. Digit Mode | ucup-team870# | WA | 3ms | 7512kb | C++14 | 1.7kb | 2023-10-01 20:40:51 | 2023-10-01 20:40:52 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef pair<int,int> P;
const int N=1e5+5,inf=(1<<30)-1;
int a[N],st[N][19];
vector<int>ps[30];
P q[N*60];
int qu(int l,int r){
if(l>r)return inf;
int t=log2(r-l+1);
return st[l][t]&st[r-(1<<t)+1][t];
}
int n;
int ask(int l,int r,int k){
if(!(l<=k && r>k))return qu(1,k)+qu(k+1,n);
return (qu(1,l-1)&qu(l+1,k)&a[r]) + (qu(k+1,r-1)&a[l]&qu(r+1,n));
}
void slv(){
cin>>n;
rep(i,1,n)cin>>a[i],st[i][0]=a[i];
rep(j,1,18){
rep(i,1,n){
if(i+(1<<j-1)<=n)st[i][j]=st[i][j-1]&st[i+(1<<j-1)][j-1];
else st[i][j]=st[i][j-1];
}
}
int cnt=0;
rep(j,0,29){
ps[j].clear();
int l=N,r=0;
rep(i,1,n){
if(a[i]&(1<<j))continue;
l=min(l,i); r=max(r,i);
if(ps[j].size()<2)ps[j].push_back(i);
}
if(!r || l==r)continue;
rep(i,1,n){
if(i!=l)q[++cnt]={i,l};
if(i!=r)q[++cnt]={i,r};
}
}
int ans=qu(1,n-1)+qu(n,n);
rep(i,1,cnt){
auto [l,r]=q[i];
if(l>r)swap(l,r);
ans=max(ans,ask(l,r,n-1));
rep(j,0,29){
if(ps[j].size()<2)continue;
int x1=ps[j][0],x2=ps[j][1],L;
if(l<x1){
L=(r==x1||r==x2)?l:x1;
}
else if(l==x1)L=(r==x2)?l:min(x2,l);
else L=x1;
ans=max(ans,ask(l,r,L));
}
}
cout<<ans<<'\n';
}
int main() {
IOS
int T;cin>>T;
while(T--)slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7512kb
input:
5 9 99 999 99999 999999
output:
999999 999999 999999 999999 999999
result:
wrong answer 1st numbers differ - expected: '45', found: '999999'