QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640609#9426. Relearn through ReviewNuj#WA 209ms9828kbC++141.5kb2024-10-14 14:42:472024-10-14 14:42:47

Judging History

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

  • [2024-10-14 14:42:47]
  • 评测
  • 测评结果:WA
  • 用时:209ms
  • 内存:9828kb
  • [2024-10-14 14:42:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<endl
ll a[300005],pre[300005],suf[300005],b[300005],c[300005],ans,k;
void solve(int l,int r,ll now){
	if(l==r) return ;
	int mid=l+r>>1;
	pre[l-1]=suf[mid+1]=0;
	int cntl=0,cntr=0;
	for(int i=l;i<=mid;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
	for(int i=mid;i>=l;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
	for(int i=l;i<=mid;i++) b[++cntl]=__gcd(pre[i-1],__gcd(suf[i+1],abs(a[i]+k)));
	pre[mid]=suf[r+1]=0;
	for(int i=mid+1;i<=r;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
	for(int i=r;i>mid;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
	for(int i=mid+1;i<=r;i++) c[++cntr]=__gcd(pre[i-1],__gcd(suf[i+1],abs(a[i]-k)));
	sort(b+1,b+cntl+1),cntl=unique(b+1,b+cntl+1)-b-1;
	sort(c+1,c+cntr+1),cntr=unique(c+1,c+cntr+1)-c-1;
	for(int i=1;i<=cntl;i++) for(int j=1;j<=cntr;j++) ans=max(ans,__gcd(now,__gcd(b[i],c[j])));
	solve(l,mid,__gcd(now,pre[r])),solve(mid+1,r,__gcd(now,suf[l]));
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;cin>>t;
	while(t--){
		int n;cin>>n>>k,ans=1;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=n;i;i--) a[i]-=a[i-1];
		for(int i=1;i<=n;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
		suf[n+1]=0;for(int i=n;i;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
		for(int i=1;i<=n;i++) ans=max(ans,__gcd(pre[i-1],__gcd(suf[i+1],abs(a[i]+k))));
//		for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
		solve(1,n,0),cout<<ans<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6 2
5 3 13 8 10 555
3 0
3 6 9

output:

5
3

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 209ms
memory: 9828kb

input:

100000
1 608611451460421713
33155506392034032
1 743116173559300609
6138108577573005
7 364454564010802125
657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115
4 316648374341335221
365788422120542814 182894211060271407 731...

output:

641766957852455745
749254282136873614
657035115675878115
182894211060271407
880411769063535667
560553564512176618
183698346865682381
962990836390050009
616597869896951268
878097339332572161
188820994675344528
997057718507559252
949074379610491450
37337367838628559
632093288650732211
3771217139073309...

result:

wrong answer 176th lines differ - expected: '166854808842365195', found: '333709617684730390'