QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693689#9426. Relearn through Reviewyld#WA 165ms3700kbC++201.3kb2024-10-31 16:34:322024-10-31 16:34:34

Judging History

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

  • [2024-10-31 16:34:34]
  • 评测
  • 测评结果:WA
  • 用时:165ms
  • 内存:3700kb
  • [2024-10-31 16:34:32]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'