QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#650517#6521. Swapping OperationWrongAnswer_90RE 2ms32428kbC++235.6kb2024-10-18 15:28:182024-10-18 15:28:19

Judging History

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

  • [2024-10-18 15:28:19]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:32428kb
  • [2024-10-18 15:28:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=1e9+7,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int n,a[100010],F[17][100010];
	int nex[30][100010];
	int pre[100010],suf[100010];
	inline int ask(int l,int r)
	{
		if(l>r)return (1<<30)-1;
		int k=__lg(r-l+1);
		return F[k][l]&F[k][r-(1<<k)+1];
	}
	inline void mian()
	{
		read(n);
		for(int i=1;i<=n;++i)read(a[i]),F[0][i]=a[i];
		for(int i=1;i<17;++i)
		{
			for(int j=1;j+(1<<i)-1<=n;++j)
			F[i][j]=F[i-1][j]&F[i-1][j+(1<<(i-1))];
		}
		for(int i=29;i>=0;--i)
		{
			nex[n+1][i]=n+1;
			for(int j=n;j>=1;--j)
			{
				if(!(a[j]>>i&1))nex[i][j]=j;
				else nex[i][j]=nex[i][j+1];
			}
		}
		int ans=0;
		pre[0]=suf[n+1]=(1<<30)-1;
		for(int i=1;i<=n;++i)pre[i]=pre[i-1]&a[i];
		for(int i=n;i>0;--i)suf[i]=suf[i+1]&a[i];
		for(int i=1;i<n;++i)Mmax(ans,pre[i]+suf[i+1]);
		for(int i=1;i<n;++i)
		{
			if(pre[i]!=pre[i-1])
			{
				for(int j=i+1;j<=n;++j)
				{
					int pr=pre[i-1]&a[j],nx=suf[j+1]&a[i];
					Mmax(ans,pr+(nx&ask(i+1,j-1)));
					Mmax(ans,(pr&ask(i+1,j-1))+nx);
					vi ve;
					for(int k=0;k<30;++k)
					{
						if((pr>>k&1)&&(nex[k][i+1]<j))
						Mmax(ans,(pr&ask(i+1,nex[k][i+1]-1))+(nx&ask(nex[k][i+1],j)));
					}
				}
			}
		}
		write(ans,'\n');
	}
	inline void Mian()
	{
		int T=1;
		read(T);
		while(T--)mian();
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0); 
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	double st=clock();
	WrongAnswer_90::Mian();
	double ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 32428kb

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
Runtime Error

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: