QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401804 | #6521. Swapping Operation | ciuim | WA | 10ms | 3732kb | C++14 | 2.1kb | 2024-04-29 14:20:03 | 2024-04-29 14:20:03 |
Judging History
answer
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define reg register
#define fo(a,b,c) for(reg ll a=b;a<=c;++a)
#define re(a,b,c) for(reg ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define fi first
#define pb push_back
#define se second
#define ite set<ll> ::iterator
using namespace std;
const ll mod=1e9+7;
inline ll gi()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
ll _=1;
const ll inf=1e17+5;
const ll N=100005;
ll a[N],pr[N],sf[N],lim=(1ll<<31)-1,ans=0,n;
void go()
{
pr[0]=lim,sf[n+1]=lim;
fo(i,1,n)
{
pr[i]=pr[i-1]&a[i];
}
re(i,n,1)
{
sf[i]=sf[i+1]&a[i];
}
fo(i,1,n-1)
{
ans=max(ans,pr[i]+sf[i+1]);
}
}
void wk(ll id)
{
pr[0]=lim,sf[n+1]=a[id];
fo(i,1,n)
{
if(i==id)
{
pr[i]=pr[i-1];
continue;
}
pr[i]=pr[i-1]&a[i];
}
re(i,n,1)
{
sf[i]=sf[i+1]&a[i];
}
for(ll l=id,r;l<=n;l=r+1)
{
r=l+1;
while(sf[r+1]==sf[l+1]) r++;
fo(i,l,n)
{
ans=max(ans,(pr[l]&a[l])+sf[l+1]);
}
}
}
void sol()
{
ans=0;
vector<ll> z,y;
n=gi();
fo(i,1,n) a[i]=gi();
go();
pr[0]=lim,sf[n+1]=lim;
fo(i,1,n)
{
pr[i]=pr[i-1]&a[i];
if(pr[i]!=pr[i-1])
{
z.pb(i);
}
}
re(i,n,1)
{
sf[i]=sf[i+1]&a[i];
if(sf[i]!=sf[i+1])
{
y.pb(i);
}
}
for(ll id1:z)
{
for(ll id2:y)
{
swap(a[id1],a[id2]);
go();
swap(a[id1],a[id2]);
}
}
for(ll id1:z)
{
wk(id1);
}
reverse(a+1,a+1+n);
for(ll id2:y)
{
wk(n-id2+1);
}
cout<<ans;
}
int main()
{
_=gi();
while(_--)
{
sol();
printf("\n");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
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
Wrong Answer
time: 10ms
memory: 3728kb
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:
890299519 923642535 960163633 963497255 906186590 923065154 979836345 771417883 973791353 897446548 920223968 969979000 494498965 917264022 981686922 827513928 988685740 989181315 729655322 863912714 968789214 934333526 924124296 964130484 971937793 918136308 977368039 980800625 551789116 973760189 ...
result:
wrong answer 1st numbers differ - expected: '999397418', found: '890299519'