QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196628#6522. Digit Modeucup-team870#WA 3ms7512kbC++141.7kb2023-10-01 20:40:512023-10-01 20:40:52

Judging History

你现在查看的是最新测评结果

  • [2023-10-01 20:40:52]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7512kb
  • [2023-10-01 20:40:51]
  • 提交

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'