QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#857442 | #9426. Relearn through Review | Moemi_ | WA | 243ms | 5864kb | C++20 | 2.7kb | 2025-01-15 18:14:53 | 2025-01-15 18:14:55 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <numeric>
#define sc_int(x) scanf("%d", &x)
#define x first
#define y second
#define pb push_back
using namespace std;
const int N = 1e6 + 10, MOD = 998244353;
const int INF = 1e9;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<char, int> PCI;
typedef pair<string, string> PSS;
LL n, m, k;
LL a[N];
struct node
{
int l, r;
LL w;
}tr[N * 4];
void pushup(int u)
{
tr[u].w = __gcd(tr[u << 1].w, tr[u << 1 | 1].w);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if(l == r)
{
tr[u].w = abs(a[l]);
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
LL query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].w;
LL ans = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) ans = __gcd(ans, query(u << 1, l, r));
if(r > mid) ans = __gcd(ans, query(u << 1 | 1, l, r));
return ans;
}
void solve()
{
cin >> n >> k;
vector<LL> s(n + 1), rs(n + 2);
vector<LL> b(n + 1);
for(int i = 1; i <= n; i ++)
{
cin >> b[i];
a[i] = b[i] - b[i - 1];
// cout << a[i] << " ";
}
// cout << endl;
build(1, 1, n);
// cout << query(1, 3, 4) << endl;
vector<int> modify;
for(int i = 1; i <= n; i ++)
{
s[i] = abs(__gcd(s[i - 1], a[i]));
if(s[i] != s[i - 1]) modify.pb(i - 1);
}
// for(auto t : modify) cout << t << " ";
// cout << endl;
for(int i = n; i >= 1; i --) rs[i] = abs(__gcd(rs[i + 1], a[i]));
LL ans = s[n];
for(int i = 1; i <= n; i ++)
{
ans = max(ans, abs(__gcd(__gcd(s[i - 1], rs[i + 1]), s[i] + k)));
}
for(int i = n; i >= 1; i --)
{
for(auto t : modify)
{
if(t >= i) break;
LL res = query(1, t + 2, i - 1);
res = __gcd(res, __gcd(s[t], rs[i + 1]));
res = __gcd(res, __gcd(a[t + 1] + k, a[i] - k));
ans = max(ans, res);
}
}
cout << ans << endl;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5864kb
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: 243ms
memory: 5736kb
input:
100000 1 608611451460421713 33155506392034032 1 743116173559300609 6138108577573005 7 364454564010802125 657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115 4 316648374341335221 365788422120542814 182894211060271407 731...
output:
641766957852455745 749254282136873614 657035115675878115 3 1 560553564512176618 1 1 616597869896951268 6 188820994675344528 997057718507559252 949074379610491450 37337367838628559 632093288650732211 377121713907330928 356502546608886970 789177332497135009 1 2 134561004312215460 3 1 2 809535299113892...
result:
wrong answer 4th lines differ - expected: '182894211060271407', found: '3'