QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196725#6521. Swapping Operationucup-team870WA 0ms7792kbC++171.9kb2023-10-01 21:49:322023-10-01 21:49:33

Judging History

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

  • [2023-10-01 21:49:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7792kb
  • [2023-10-01 21:49:32]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(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[19][N],pre[N],suf[N], l2[N];
vector<int>ps[30];
P q[N*60];
int qu(int l,int r){
    int t=l2[r-l+1];
    return st[l][t]&st[r-(1<<t)+1][t];
}
int qu1(int l,int r){
    if(l>r)return inf;
    int t=l2[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 (pre[l-1]&qu1(l+1,k)&a[r]) + (qu1(k+1,r-1)&a[l]&suf[r+1]);
}
void slv(){
    cin>>n;
    rep(i,1,n)cin>>a[i],st[0][i]=a[i];
    pre[0]=suf[n+1]=inf;
    rep(i,1,n)pre[i]=pre[i-1]&a[i];
    per(i,n,1)suf[i]=suf[i+1]&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){
            q[++cnt]={i,l}; 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,r);
            else L=x1;
            if(L>1)ans=max(ans,ask(l,r,L-1));
        }
    }
    cout<<ans<<'\n';
}
int main() {
    IOS
    rep(i,1,1e5)l2[i]=log2(i);
    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: 0ms
memory: 7792kb

input:

3
6
6 5 4 3 5 6
6
1 2 1 1 2 2
5
1 1 2 2 2

output:

6
2
2

result:

wrong answer 1st numbers differ - expected: '7', found: '6'