QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196725 | #6521. Swapping Operation | ucup-team870 | WA | 0ms | 7792kb | C++17 | 1.9kb | 2023-10-01 21:49:32 | 2023-10-01 21:49:33 |
Judging History
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'