QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401804#6521. Swapping OperationciuimWA 10ms3732kbC++142.1kb2024-04-29 14:20:032024-04-29 14:20:03

Judging History

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

  • [2024-04-29 14:20:03]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3732kb
  • [2024-04-29 14:20:03]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'