QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693689 | #9426. Relearn through Review | yld# | WA | 165ms | 3700kb | C++20 | 1.3kb | 2024-10-31 16:34:32 | 2024-10-31 16:34:34 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve()
{
int n,k;cin>>n>>k;
vector<int> a(n+1),cha(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cha[i]=a[i]-a[i-1];
vector st(n+1,vector<int>(20));
auto init=[&]()
{
for(int i=1;i<=n;i++) st[i][0]=cha[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=__gcd(st[i][j-1],st[i+(1<<j-1)][j-1]);
};
init();
// cerr<<"================\n";
// for(int i=1;i<=n;i++) cout<<cha[i]<<' ';
// cout<<endl;
map<int,int> pos;
auto getgcd=[&](int l,int r)
{
if(r<l) return 0ll;
int x=log2(r-l+1);
return __gcd(st[l][x],st[r-(1<<x)+1][x]);
};
// cerr<<getgcd(2,3)<<endl;
int ans=0;
for(int r=1;r<=n;r++)
{
for(auto [x,y]:pos)
{
int tmp=__gcd(__gcd(getgcd(y+1,r-1),cha[r]-k),getgcd(r+1,n));
tmp=__gcd(tmp,x);
ans=max(ans,tmp);
}
int tmp=__gcd(getgcd(1,r-1),cha[r]+k);
pos[tmp]=r;
}
cout<<ans<<endl;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
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: 165ms
memory: 3700kb
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 657035115675878115 3 1 0 1 0 0 6 0 3 0 37337367838628559 632093288650732211 377121713907330928 2 0 1 2 0 1 1 0 809535299113892268 0 0 0 1 1 3 0 4 557547233762973087 3 0 515597846986915098 777819466140221104 4 657659966947439521 0 926534262599314442 706331311901646081 0 4 0 551 0 30 0 66 68033752...
result:
wrong answer 1st lines differ - expected: '641766957852455745', found: '0'