QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#776582#9738. Make It DivisiblezqxWA 14ms10348kbC++232.0kb2024-11-23 19:32:072024-11-23 19:32:08

Judging History

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

  • [2024-11-27 18:44:44]
  • hack成功,自动添加数据
  • (/hack/1263)
  • [2024-11-23 19:32:08]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:10348kb
  • [2024-11-23 19:32:07]
  • 提交

answer

#include<stack>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define inf 0X7fffffff
#define int long long 
using namespace std;
const int N = 2e5 + 9;
int read(int& x) {
    int dat = 0, oko = 1; char chc = getchar();
    while (chc < '0' || chc>'9') { if (chc == '-')oko = -1; chc = getchar(); }
    while (chc >= '0' && chc <= '9') { dat = dat * 10 + chc - '0'; chc = getchar(); }
    x = dat * oko; return x;
}int T, n, k, _gcd, a[N], b[N], c[N], ans1, ans2;
int tree[N << 2], f1[N], f2[N];
stack<int>q, zero;
int gcd(int x, int y) {
    while (y) { x %= y; swap(x, y); }
    return x;
}bool check(int x) {
    for (int i = 1; i <= n; i++) {
        if (f1[i] && (c[i] + x) % (f1[i] + x))return false;
        if (f2[i] && (f2[i] + x) % (c[i] + x))return false;
    }return true;
}
void prework() {
    while (!q.empty())q.pop();
    for (int i = 1; i <= n; i++) {
        f1[i] = 0, f2[i] = 0;
        while (!q.empty() && q.top() >= c[i]) {
            f2[i] = q.top();
            q.pop();
        }if (!q.empty())f1[i] = q.top();
        q.push(c[i]);
    }
}
void solve() {
    cin >> n >> k; ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; c[i] = a[i];
    }sort(a + 1, a + 1 + n); _gcd = 0;
    prework();
    for (int i = 2; i <= n; i++) {
        _gcd = gcd(_gcd, a[i] - a[i - 1]);
    }if (!_gcd) {
        cout << k << " " << (((k + 1) * k) >> 1) << "\n";
        return;
    }for (int i = 1; i * i <= _gcd; i++) {
        if (_gcd % i)continue;
        if (a[1] + k >= i && i > a[1]) {
            if (check(i - a[i])) {
                ans1++; ans2 += i - a[1];
            }
        }int j = _gcd / i; if (i == j)continue;
        if (a[1] + k >= j && j > a[1]) {
            if (check(j - a[1])) {
                ans1++; ans2 += j - a[1];
            }
        }
    }cout << ans1 << " " << ans2 << "\n";
}
signed main() {
    cin >> T;
    while (T--)solve();
    return 0;
}
/*
3
5 10
7 79 1 7 1
2 1000000000
1 2
1 10000
1000000000
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

output:

3 8
0 0
100 5050

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 7840kb

input:

4
201 1000000000
1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...

output:

0 0
0 0
0 0
0 0

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 7872kb

input:

500
4 1000000000
8 14 24 18
4 1000000000
17 10 18 14
4 1000000000
6 17 19 19
4 1000000000
15 14 15 25
4 1000000000
16 16 5 25
4 1000000000
4 30 20 5
4 1000000000
11 4 23 9
4 1000000000
14 25 13 2
4 1000000000
18 18 1 15
4 1000000000
22 22 22 28
4 1000000000
15 17 17 10
4 1000000000
22 14 13 25
4 100...

output:

0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
...

result:

ok 500 lines

Test #4:

score: 0
Accepted
time: 14ms
memory: 10272kb

input:

1
50000 1000000000
230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 ...

output:

0 0

result:

ok single line: '0 0'

Test #5:

score: 0
Accepted
time: 14ms
memory: 8372kb

input:

1
50000 1000000000
12087 1196491 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 553146...

output:

0 0

result:

ok single line: '0 0'

Test #6:

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

input:

1
50000 1000000000
2138984 42249920 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 3581...

output:

0 0

result:

ok single line: '0 0'

Test #7:

score: -100
Wrong Answer
time: 9ms
memory: 9728kb

input:

500
39 1000000000
75 7 7 381 41 1197 177 177 41 109 109 16 1197 177 41 381 1605 381 381 7 177 177 177 177 177 177 177 177 7 7 143 143 143 143 143 653 143 823 7
61 1000000000
327 327 327 327 405153474 327 405153474 327 810306621 810306621 810306621 810306621 810306621 810306621 810306621 810306621 81...

output:

0 0
16 631530730
9 18919501
1 1
2 6878
1 2
1 1
2 10
0 0
1 110
0 0
1 36
7 4680
1 29
1 4
5 2209189
0 0
3 8
1 2
6 30769256
1000000000 500000000500000000
1 3
1000000000 500000000500000000
0 0
1 5
1 1
4 6615238
2 8233824
2 1035
1 3
6 1282
0 0
1 3
11 1617864650
2 10
0 0
1 5739
12 102215
3 1100
1000000000 ...

result:

wrong answer 2nd lines differ - expected: '25 631568356', found: '16 631530730'