QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#857442#9426. Relearn through ReviewMoemi_WA 243ms5864kbC++202.7kb2025-01-15 18:14:532025-01-15 18:14:55

Judging History

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

  • [2025-01-15 18:14:55]
  • 评测
  • 测评结果:WA
  • 用时:243ms
  • 内存:5864kb
  • [2025-01-15 18:14:53]
  • 提交

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'