QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196754#6521. Swapping Operationucup-team870TL 0ms13932kbC++172.0kb2023-10-01 22:09:162023-10-01 22:09:16

Judging History

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

  • [2023-10-01 22:09:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:13932kb
  • [2023-10-01 22:09:16]
  • 提交

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){
    // if(l>r)return inf;
    // int t=l2[r-l+1];
    int t=log2(r-l+1);
    return st[t][l]&st[t][r-(1<<t)+1];
}
int qu1(int l,int r){
    if(l>r)return inf;
    int t=l2[r-l+1];
    return st[t][l]&st[t][r-(1<<t)+1];
}
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[j][i]=st[j-1][i]&st[j-1][i+(1<<j-1)];
            else st[j][i]=st[j-1][i];
        }
    }
    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){ //不能l+1,r-1 !!!!!!!!!!!!
            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: 100
Accepted
time: 0ms
memory: 13932kb

input:

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

output:

7
3
3

result:

ok 3 number(s): "7 3 3"

Test #2:

score: -100
Time Limit Exceeded

input:

1000
100
803046221 177233942 164782937 53823867 383853667 250036100 888743479 576687945 737272231 801579441 647643785 393059353 401516062 663466861 308544510 825328494 162739603 501761995 570908380 655227403 444493122 844535039 208303132 493226172 421479971 634680694 396627047 787471115 335787136 16...

output:


result: