QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#650805 | #9426. Relearn through Review | sevenki# | WA | 3ms | 11788kb | C++17 | 2.2kb | 2024-10-18 16:34:43 | 2024-10-18 16:34:43 |
Judging History
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;
}
詳細信息
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'