QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#650805#9426. Relearn through Reviewsevenki#WA 3ms11788kbC++172.2kb2024-10-18 16:34:432024-10-18 16:34:43

Judging History

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

  • [2024-10-18 16:34:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11788kb
  • [2024-10-18 16:34:43]
  • 提交

answer

#include <bits/stdc++.h>
#define mkp make_pair
#define fi first
#define se second
#define debug(x) cerr<<"line: "<<__LINE__<<" with "<<x<<"\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using vi = vector<int>;
const int mod = 998244353;
template<class T>bool chkMin(T &x,T y){if(x>y)return x=y,true;return false;}
template<class T>bool chkMax(T &x,T y){if(x<y)return x=y,true;return false;}
template<class T>void moder(T &x){x%=mod;}
const int MAXN = 300005;
int n,k;
ll a[MAXN],cf[MAXN];
ll pre[MAXN],suf[MAXN];
bool valid(int x){return 1<=x&&x<=n;}
ll seg[MAXN<<2];
#define ls (p<<1)
#define rs (p<<1|1)
void build(int lp,int rp,int p){
	if(lp==rp){
		seg[p]=abs(cf[lp]);return;
	}int mid = (lp+rp)/2;
	build(lp,mid,ls);build(mid+1,rp,rs);
	seg[p]=__gcd(seg[ls],seg[rs]);
}
ll query(int l,int r,int lp=1,int rp=n,int p=1){
	if(l<=lp && r>=rp)return seg[p];
	int mid = (lp+rp)/2;
	if(l<=mid && r>mid)return __gcd(query(l,r,lp,mid,ls),
									query(l,r,mid+1,rp,rs));
	if(l<=mid)return query(l,r,lp,mid,ls);
	if(r>mid)return query(l,r,mid+1,rp,rs);
	assert(0);
	return 666;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cf[i]=a[i]-a[i-1];
	pre[1]=cf[1], suf[n]=abs(cf[n]);
	for(int i=2;i<=n;i++)pre[i]=__gcd(pre[i-1],abs(cf[i]));
	for(int i=n-1;i>=1;i--)suf[i]=__gcd(suf[i+1],abs(cf[i]));
	vector<int> L,R;
	pre[0]=suf[n+1]=0;
	build(1,n,1);
	for(int i=0;i<n;i++){
		if(pre[i]!=pre[i+1])L.push_back(i+1),L.push_back(i);
	}
	for(int i=n;i>=1;i--){
		if(suf[i]!=suf[i-1])R.push_back(i-1),R.push_back(i);
	}
	ll ans = pre[n];
	for(int i=1;i<=n;i++){
		ll res = abs(cf[i]);
		if(i>1)res=__gcd(res,pre[i-1]);
		if(i<n)res=__gcd(res,suf[i+1]);
		ans=max(ans,res);
	}
	for(int i : L){
		if(!valid(i))continue;
		for(int j : R){
			if(i>=j || !valid(j))continue;
			ll res = __gcd(abs(cf[i]+k),abs(cf[j]-k));
			if(i>1)res=__gcd(res,pre[i-1]);
			if(j<n)res=__gcd(res,suf[j+1]);
			if(i+1<=j-1)res=__gcd(res,query(i+1,j-1));
			ans=max(ans,res);
		}
	}
	cout<<ans<<"\n";
}
signed main() {
	//cerr<<(&s1-&s2)/1024.0/1024<<" ";
	cin.tie(nullptr)->sync_with_stdio(false);
	int T;cin>>T;
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 9756kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st lines differ - expected: '641766957852455745', found: '0'