QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#631981#9426. Relearn through Reviewretired_midlightsWA 129ms12676kbC++141.5kb2024-10-12 11:16:552024-10-12 11:16:55

Judging History

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

  • [2024-10-12 11:16:55]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:12676kb
  • [2024-10-12 11:16:55]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (int)a; i <= (int)b; i ++)
#define per(i, a, b) for(int i = (int)a; i >= (int)b; i --)
#define ll long long
using namespace std;
const int maxn = 300010;
int n, lg[maxn];
ll k, a[maxn], pre[maxn], suf[maxn], b[maxn][20];
ll query(int l, int r) {
    if(l > r) return 0;
    int k = lg[r - l + 1];
    return __gcd(b[l][k], b[r - (1 << k) + 1][k]);
}
void solve() {
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n - 1) b[i][0] = abs(a[i] - a[i + 1]);
    rep(j, 1, 18) rep(i, 1, n - (1 << j))
        b[i][j] = __gcd(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
    pre[1] = a[1];
    vector < int > positions;
    rep(i, 2, n) {
        pre[i] = __gcd(pre[i - 1], a[i]);
        if(pre[i] != pre[i - 1]) positions.push_back(i - 1);
    }
    positions.push_back(n);
    suf[n] = a[n];
    per(i, n - 1, 1) suf[i] = __gcd(suf[i + 1], a[i]);
    ll res = pre[n];
    rep(r, 1, n) {
        for(auto l : positions) {
            if(l > r) break;
            // cout << l << " " << r << endl;
            ll cur = __gcd(pre[l], suf[r + 1]);
            cur = __gcd(cur, __gcd(a[r] + k, query(l + 1, r - 1)));
            res = max(res, cur);
        }
    }
    cout << res << '\n';
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios :: sync_with_stdio(false);
    cin.tie(0);
    lg[1] = 0;
    rep(i, 2, 300000) lg[i] = lg[i >> 1] + 1;
    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: 0ms
memory: 12216kb

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: 129ms
memory: 12676kb

input:

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

output:

33155506392034032
6138108577573005
657035115675878115
3
1
98423435849394582
1
3
484915690810412536
3
149180825015886938
361813583202892479
915781395066183375
37337367838628559
632093288650732211
1
2
494408344393555851
1
1
118387461231999184
1
383091938972089281
1
809535299113892268
58078718587567409...

result:

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