QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#631981 | #9426. Relearn through Review | retired_midlights | WA | 129ms | 12676kb | C++14 | 1.5kb | 2024-10-12 11:16:55 | 2024-10-12 11:16:55 |
Judging History
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'