QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645624#9426. Relearn through ReviewSorahISAWA 220ms19180kbC++2311.1kb2024-10-16 19:14:552024-10-16 19:14:56

Judging History

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

  • [2024-10-16 19:14:56]
  • 评测
  • 测评结果:WA
  • 用时:220ms
  • 内存:19180kb
  • [2024-10-16 19:14:55]
  • 提交

answer

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

void solve() {
    int N, K; cin >> N >> K;
    
    vector<int> A(N), dif;
    for (int &x : A) cin >> x;
    adjacent_difference(ALL(A), back_inserter(dif));
    dif.eb(-A[N-1]);
    
    vector<array<int, 2>> pre(N+1), suf(N+1);
    for (int i = 0; i <= N; ++i) {
        pre[i][0] = gcd((i > 0 ? pre[i-1][0] : 0), abs(dif[i]));
        pre[i][1] = max(gcd((i > 0 ? pre[i-1][1] : 0), abs(dif[i])), gcd((i > 0 ? pre[i-1][0] : 0), abs(dif[i] + K)));
    }
    for (int i = N; i >= 0; --i) {
        suf[i][0] = gcd((i < N ? suf[i+1][0] : 0), abs(dif[i]));
        suf[i][1] = max(gcd((i < N ? suf[i+1][1] : 0), abs(dif[i])), gcd((i < N ? suf[i+1][0] : 0), abs(dif[i] - K)));
    }
    
    int ans = pre[N][0];
    for (int i = 0; i+1 <= N; ++i) chmax(ans, gcd(pre[i][1], suf[i+1][1]));
    print(ans);
}

int32_t main() {
    fastIO();
    
    int t = 1; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>

using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
//     static_assert(D >= 1, "Vector dimension must be greater than zero!");
//     template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };

// template <typename T> struct Vec<1, T> : vector<T> {
//     Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
    fprintf(stdout, "%s", "\u001b[36m"), \
    _P(__VA_ARGS__), \
    fprintf(stdout, "%s", "\u001b[0m")

deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif

inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) { cerr << _t; }

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    _color.emplace_back(_color.back()), ++_color.back()[3];
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    _color.emplace_back(_color.back()), ++_color.back()[3];
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        _color.emplace_back(_color.back()), ++_color.back()[3];
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        _color.emplace_back(_color.back()), ++_color.back()[3];
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif

/**
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
 *                            iiiiii         iiiiiiiiii       iiiiiiiiiiiiii                                       
 *                       iiiiiiiiiiiii   iiiiiii    iiii    iiiiiiiiiiiiiii                          ii   iiii     
 *                    iiiiiiii     iiiiiiiii         iiii       iiii iii              iii          iiiiiiiiii      
 *                 iiiiiii          iiiiii           iiii    iiii   ii           iiiiiiiiii      iiii iiii         
 *               iiiiii            iiiii             iiii iiii        iii      iiii    iiiiiiiiiiiiiiiii  ii       
 *             iiiiii            iiiiiii            iiiiiii       iiiiiiii   iii    iiiiiiiiiiiiii iii  iiii       
 *           iiiiii             iiiiiii            iiiii   ii   iiii       iiiiiiiiiii iiii  iii iiii iiii      iii
 *          iiiii              iiiiiiii       ii        iiiii iiii    iiiiiiiii        iii iii  iii  iii  ii  iiii 
 *        iiiiii              iiiiiiii      iiiii     iiiii iiiiiiiiiiiiiiii         iii  iii  ii  iii  iii iiii   
 *       iiiii                 iiiiii     iiii     iiiiii iiiiiii    iii iii       iiii  ii   i   ii  iii  iii     
 *     iiiiii                            iiii  iiiiiiiiiiiiiii       iii iiii   iiiii  iii  ii  iii  iii  ii       
 *    iiiii                              iiiiiiii iiiiiiiiii       iiii   iiiiiiiii            ii  iii  ii         
 *   iiiii                                     iiiiii  iiii      iiiii              iii      ii   ii  i            
 * iiiiii                                  iiiiiiii   iiiii    iiiii                        ii  ii   ii            
 * iiiii                                iiii  iiii    iiiiiiiiiiii                             ii                  
 *  iii                              iiii   iiii       iiiiiiii                                                    
 *                                iiiii   iiii                                                                     
 *                              iiii     iiii                                                                      
 *                            iiii    iiiii                                                                        
 *                          iii     iiiii                                                                          
 *                        iii     iiiii                                                                            
 *                       iii   iiiiii                                                                              
 *                       iiiiiiiii                                                                                 
 *                       iiiiii                                                                                    
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
**/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

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: 0
Accepted
time: 220ms
memory: 3708kb

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
182894211060271407
880411769063535667
560553564512176618
183698346865682381
962990836390050009
616597869896951268
878097339332572161
188820994675344528
997057718507559252
949074379610491450
37337367838628559
632093288650732211
3771217139073309...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 75ms
memory: 3820kb

input:

1000
71 451750502977198411
701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 701513700102652904 7015137...

output:

701513700102652904
628264251002959880
866034990978685601
718723820869997225
525309136656747615
453291245761058554
420366973911241294
500173849665919725
16701821680586640
794711320668492112
799961738480944637
963500289005941882
190368877908873112
973069943210898565
629019279628092667
1921616220783983...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 69ms
memory: 4224kb

input:

100
5516 16561406822518327
121909691713696369 226403713182578971 940446193219943418 505054437099599243 505054437099599243 383144745385902874 470223096609971709 714042480037364447 417976085875530408 783705161016619515 888199182485502117 208988042937765204 330897734651461573 818536501506247049 7488738...

output:

17415670244813767
678667366385241526
375190657607916623
343566816881610443
293858497297593293
545063989451911922
101584687520632945
923261939978554511
245471164671296626
996567332718295422
871411820593738277
999473841903341933
575286590792404442
298698210937205101
265822932252018295
4113318308187297...

result:

ok 100 lines

Test #5:

score: 0
Accepted
time: 69ms
memory: 9128kb

input:

10
2651 1901143105096273
954803577560210292 636535718373473528 159133929593368382 159133929593368382 954803577560210292 477401788780105146 636535718373473528 636535718373473528 954803577560210292 636535718373473528 318267859186736764 636535718373473528 636535718373473528 318267859186736764 795669647...

output:

159133929593368382
793024501989621764
454059328664071477
113729984568648330
507863600649451091
779491329333959710
821665805532903623
384579792180981183
356029896436006899
340683633028457433

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 75ms
memory: 11812kb

input:

3
31056 13873801082583029
316385357210519324 316385357210519324 316385357210519324 949156071631557972 632770714421038648 949156071631557972 316385357210519324 316385357210519324 316385357210519324 316385357210519324 632770714421038648 949156071631557972 316385357210519324 316385357210519324 31638535...

output:

316385357210519324
399693130963531970
229449205713014908

result:

ok 3 lines

Test #7:

score: 0
Accepted
time: 73ms
memory: 18776kb

input:

1
300000 309955051600565498
497784205512766609 995568411025533218 995568411025533218 995568411025533218 995568411025533218 497784205512766609 497784205512766609 995568411025533218 995568411025533218 995568411025533218 497784205512766609 995568411025533218 497784205512766609 497784205512766609 497784...

output:

497784205512766609

result:

ok single line: '497784205512766609'

Test #8:

score: 0
Accepted
time: 11ms
memory: 19180kb

input:

1
300000 1
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7...

output:

7

result:

ok single line: '7'

Test #9:

score: 0
Accepted
time: 15ms
memory: 17320kb

input:

1
300000 60
66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 ...

output:

66

result:

ok single line: '66'

Test #10:

score: 0
Accepted
time: 40ms
memory: 18024kb

input:

1
300000 522555291
775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355392 775151491735355...

output:

721916083

result:

ok single line: '721916083'

Test #11:

score: 0
Accepted
time: 8ms
memory: 18092kb

input:

1
300000 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 15ms
memory: 18736kb

input:

1
300000 3
64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 6...

output:

4

result:

ok single line: '4'

Test #13:

score: 0
Accepted
time: 38ms
memory: 18740kb

input:

1
300000 634838941
826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341888 826705280146341...

output:

720994598

result:

ok single line: '720994598'

Test #14:

score: 0
Accepted
time: 38ms
memory: 18680kb

input:

1
300000 236226483
980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362176 980299602173362...

output:

721363081

result:

ok single line: '721363081'

Test #15:

score: -100
Wrong Answer
time: 31ms
memory: 3860kb

input:

75000
4 0
1 1 1 1
4 1
1 1 1 1
4 2
1 1 1 1
4 3
1 1 1 1
4 4
1 1 1 1
4 0
2 1 1 1
4 1
2 1 1 1
4 2
2 1 1 1
4 3
2 1 1 1
4 4
2 1 1 1
4 0
3 1 1 1
4 1
3 1 1 1
4 2
3 1 1 1
4 3
3 1 1 1
4 4
3 1 1 1
4 0
4 1 1 1
4 1
4 1 1 1
4 2
4 1 1 1
4 3
4 1 1 1
4 4
4 1 1 1
4 0
5 1 1 1
4 1
5 1 1 1
4 2
5 1 1 1
4 3
5 1 1 1
4 4
5 ...

output:

1
2
3
4
5
1
2
1
2
1
1
2
3
2
1
1
2
3
4
1
1
2
1
4
5
1
1
1
1
1
1
2
1
2
1
1
1
1
1
1
1
2
1
2
1
1
1
1
1
1
1
2
1
2
1
1
2
1
2
1
1
2
3
2
1
1
2
1
2
1
1
2
1
2
1
1
1
3
1
1
1
2
1
2
1
1
1
3
1
1
1
2
3
4
1
1
1
1
1
1
1
2
1
4
1
1
1
1
2
1
1
2
1
2
1
1
2
1
4
1
1
2
1
4
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

wrong answer 107th lines differ - expected: '2', found: '1'