QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#645461	#6399. Classic: Classical Problem	crimsonsunset^#	TL	3114ms	3876kb	C++20	2.3kb	2024-10-16 18:30:38	2024-10-16 18:30:38

Judging History

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

[2024-10-16 18:30:38]
评测

测评结果：TL
用时：3114ms
内存：3876kb

查看

[2024-10-16 18:30:38]
提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
#define int ll
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rnd(1329);

int mod;

int fastpow(int a, int b) {
    if (b == 0) return 1;
    int t = fastpow(a, b / 2);
    t = 1ll * t * t % mod;
    if (b % 2) {
        t = 1ll * t * a % mod;
    }
    return t;
}

int lol(int a) {
    return 1 * fastpow(a, mod - 2);
}

bool used[(int)2e5 + 10];

void solve() {
    int n, p;
    cin >> n >> p;
    mod = p;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (auto e : a) used[e] = 1;
    if (used[0] == 0) {
//        cout << "lol ";
        cout << "1 1\n0\n";
        for (auto e : a) used[e] = 0;
        return;
    }
    sort(all(a));
    if (n == 1) {
        for (auto e : a) used[e] = 0;
        cout << p << ' ' << 1 << '\n';
        for (int i = 0; i < p; ++i) cout << i << ' ';
        cout << '\n';
        return;
    }
    int ans = 0;
    while (used[ans]) ans++;
    set<int> anss; anss.insert(1);
    if (ans == 1) anss.insert(0);
    for (auto e : a) {
        if (e == 0) continue;
        bool ok = 1;
        int x = lol(e);
//        cout << x << '\n';
        for (int i = 0; i < 500; ++i) {
            if (ans == 1) break;
            int j = rnd() % (ans - 1) + 1;
            if (used[1ll * j * fastpow(x, mod - 2) % mod]) continue;
            ok = 0;
            break;
        }
        if (!ok) continue;
        for (int j = 1; j < ans; ++j) {
            if (used[1ll * j * fastpow(x, mod - 2) % mod]) continue;
            ok = 0;
            break;
        }
        if (!ok) continue;
        if (ans == p) {
            anss.insert(x);
            continue;
        }
        if (used[1ll * ans * fastpow(x, mod - 2) % mod]) {
            anss.clear();
            while (ans < p && used[1ll * ans * fastpow(x, mod - 2) % mod]) ans++;
        }
        anss.insert(x);
    }
    cout << anss.size() << ' ' << ans << '\n';
    for (auto e : anss) cout << e << ' '; cout << '\n';
    for (auto e : a) used[e] = 0;
}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) solve();
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok 6 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3488kb

input:

output:

result:

ok 14 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 62 lines

Test #5:

score: 0

Accepted

time: 2ms

memory: 3536kb

input:

output:

7 1
0 1 2 3 4 5 6 
1 1
0
1 2
1 
1 1
0
1 2
4 
1 1
0
1 3
1 
1 1
0
1 2
5 
1 1
0
2 2
1 5 
1 1
0
2 2
4 5 
1 1
0
1 4
1 
1 1
0
1 2
2 
1 1
0
1 3
2 
1 1
0
1 3
4 
1 1
0
3 3
1 2 4 
1 1
0
2 2
2 5 
1 1
0
1 3
2 
1 1
0
1 3
4 
1 1
0
1 5
1 
1 1
0
1 2
3 
1 1
0
2 2
1 3 
1 1
0
2 2
3 4 
1 1
0
1 3
1 
1 1
0
1 3
3 
1 1
0
1...

result:

ok 254 lines

Test #6:

score: 0

Accepted

time: 28ms

memory: 3608kb

input:

output:

11 1
0 1 2 3 4 5 6 7 8 9 10 
1 1
0
1 2
1 
1 1
0
1 2
6 
1 1
0
1 3
1 
1 1
0
1 2
4 
1 1
0
2 2
1 4 
1 1
0
2 2
4 6 
1 1
0
1 4
1 
1 1
0
1 2
3 
1 1
0
2 2
1 3 
1 1
0
1 3
6 
1 1
0
2 3
1 6 
1 1
0
2 2
3 4 
1 1
0
3 2
1 3 4 
1 1
0
1 3
6 
1 1
0
1 5
1 
1 1
0
1 2
9 
1 1
0
2 2
1 9 
1 1
0
2 2
6 9 
1 1
0
1 3
1 
1 1
0
...

result:

ok 4094 lines

Test #7:

score: 0

Accepted

time: 143ms

memory: 3640kb

input:

output:

13 1
0 1 2 3 4 5 6 7 8 9 10 11 12 
1 1
0
1 2
1 
1 1
0
1 2
7 
1 1
0
1 3
1 
1 1
0
1 2
9 
1 1
0
2 2
1 9 
1 1
0
2 2
7 9 
1 1
0
1 4
1 
1 1
0
1 2
10 
1 1
0
2 2
1 10 
1 1
0
1 3
7 
1 1
0
2 3
1 7 
1 1
0
2 2
9 10 
1 1
0
3 2
1 9 10 
1 1
0
1 3
7 
1 1
0
1 5
1 
1 1
0
1 2
8 
1 1
0
2 2
1 8 
1 1
0
2 2
7 8 
1 1
0
1 3...

result:

ok 16382 lines

Test #8:

score: 0

Accepted

time: 224ms

memory: 3548kb

input:

output:

17 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
1 1
0
1 2
1 
1 1
0
1 2
9 
1 1
0
1 3
1 
1 1
0
1 2
6 
1 1
0
2 2
1 6 
1 1
0
2 2
6 9 
1 1
0
1 4
1 
1 1
0
1 2
13 
1 1
0
2 2
1 13 
1 1
0
1 3
9 
1 1
0
2 3
1 9 
1 1
0
2 2
6 13 
1 1
0
3 2
1 6 13 
1 1
0
1 3
9 
1 1
0
1 5
1 
1 1
0
1 2
7 
1 1
0
2 2
1 7 
1 1
0
2 2
7 ...

result:

ok 23528 lines

Test #9:

score: 0

Accepted

time: 170ms

memory: 3836kb

input:

output:

19 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1 1
0
1 2
1 
1 1
0
1 2
10 
1 1
0
1 3
1 
1 1
0
1 2
13 
1 1
0
2 2
1 13 
1 1
0
2 2
10 13 
1 1
0
1 4
1 
1 1
0
1 2
5 
1 1
0
2 2
1 5 
1 1
0
1 3
10 
1 1
0
2 3
1 10 
1 1
0
2 2
5 13 
1 1
0
3 2
1 5 13 
1 1
0
1 3
10 
1 1
0
1 5
1 
1 1
0
1 2
4 
1 1
0
2 2
1 4 
...

result:

ok 21052 lines

Test #10:

score: 0

Accepted

time: 172ms

memory: 3800kb

input:

10000
9 83
60 35 63 59 58 81 0 13 71
1 5
0
1 7
0
2 61
39 0
2 7
0 4
1 7
0
2 19
0 14
1 2
0
3 23
14 10 0
3 11
0 5 2
1 5
0
2 7
0 4
2 3
0 2
2 3
0 1
1 13
0
5 47
10 2 34 15 0
1 2
0
1 17
0
1 11
0
2 7
1 0
1 7
0
2 23
0 17
2 13
10 0
2 7
1 0
6 31
19 13 6 29 0 24
4 23
0 5 18 17
2 19
0 5
1 7
0
2 13
7 0
3 17
0 6 1...

output:

2 3
38 76 
5 1
0 1 2 3 4 
7 1
0 1 2 3 4 5 6 
1 2
36 
1 2
2 
7 1
0 1 2 3 4 5 6 
1 2
15 
2 1
0 1 
2 2
5 7 
2 2
6 9 
5 1
0 1 2 3 4 
1 2
2 
1 2
2 
1 2
1 
13 1
0 1 2 3 4 5 6 7 8 9 10 11 12 
4 2
18 22 24 33 
2 1
0 1 
17 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
11 1
0 1 2 3 4 5 6 7 8 9 10 
1 2
1 
7 1
0 ...

result:

ok 20000 lines

Test #11:

score: 0

Accepted

time: 697ms

memory: 3604kb

input:

10000
10 11
6 8 0 1 7 3 2 9 4 5
21 23
21 19 10 17 11 20 6 3 2 18 9 16 13 14 4 12 8 7 1 0 15
7 7
6 2 4 0 1 5 3
17 19
4 6 5 11 17 15 0 10 3 8 12 18 13 7 9 2 14
15 17
11 15 8 2 12 3 1 13 16 6 7 0 9 10 5
2 2
0 1
2 2
0 1
33 37
11 20 9 16 19 32 33 31 3 29 36 10 8 25 22 17 5 6 15 28 14 0 4 27 18 12 34 21 3...

output:

1 10
1 
1 19
4 
6 7
1 2 3 4 5 6 
1 14
14 
1 14
12 
1 2
1 
1 2
1 
2 21
21 24 
1 8
8 
6 7
1 2 3 4 5 6 
10 11
1 2 3 4 5 6 7 8 9 10 
1 22
22 
1 6
1 
1 10
11 
1 26
22 
2 3
1 2 
1 14
16 
22 23
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
2 4
2 6 
1 18
3 
6 7
1 2 3 4 5 6 
1 2
1 
1 8
7 
1 28
15...

result:

ok 20000 lines

Test #12:

score: 0

Accepted

time: 327ms

memory: 3656kb

input:

10000
4 13
4 5 0 6
12 31
0 16 11 13 3 24 26 21 20 6 5 19
12 43
29 21 40 23 31 24 27 17 30 10 0 42
3 3
0 2 1
15 47
41 46 0 44 17 39 30 4 12 14 36 28 27 31 10
1 5
0
5 11
6 2 0 5 1
6 13
11 0 7 5 10 6
5 17
15 0 9 12 11
6 13
0 5 2 12 11 7
15 43
14 28 13 24 40 29 37 9 27 0 34 39 15 12 2
1 3
0
8 17
15 6 0 ...

output:

3 2
8 10 11 
1 6
6 
2 3
33 41 
2 3
1 2 
3 3
31 37 41 
5 1
0 1 2 3 4 
2 3
1 2 
2 3
4 8 
4 2
2 8 10 14 
1 3
12 
1 4
14 
3 1
0 1 2 
1 4
8 
2 1
0 1 
3 2
4 9 10 
4 2
1 3 5 12 
1 2
3 
5 2
3 12 15 16 18 
7 1
0 1 2 3 4 5 6 
5 2
2 5 15 16 18 
10 2
2 6 8 11 19 25 27 29 34 35 
3 2
2 7 9 
1 2
2 
3 3
7 14 15 
2 ...

result:

ok 20000 lines

Test #13:

score: 0

Accepted

time: 390ms

memory: 3612kb

input:

10000
13 19
13 6 0 9 15 2 4 10 3 5 11 12 14
5 11
5 8 10 0 6
2 3
0 1
1 2
0
10 19
6 16 2 1 17 0 4 10 5 7
4 7
0 1 4 2
41 73
55 47 13 35 18 68 3 25 67 36 70 69 62 37 56 64 49 72 12 0 4 17 31 8 66 63 2 16 65 60 24 26 7 21 33 52 54 39 29 53 71
1 3
0
26 61
43 0 37 54 47 49 17 38 19 28 35 18 39 36 33 34 8 2...

output:

1 6
13 
2 3
7 9 
1 2
1 
2 1
0 1 
1 4
10 
3 3
1 2 4 
1 12
72 
3 1
0 1 2 
2 5
10 17 
1 7
11 
1 7
27 
1 4
8 
2 3
1 2 
2 3
1 2 
1 2
1 
1 2
2 
1 6
6 
1 8
31 
1 4
13 
1 3
3 
1 4
12 
3 5
1 2 7 
1 7
5 
1 2
4 
3 1
0 1 2 
2 1
0 1 
2 4
4 6 
1 2
4 
2 2
1 10 
2 4
10 12 
2 4
4 6 
1 2
2 
2 6
3 5 
7 1
0 1 2 3 4 5 6...

result:

ok 20000 lines

Test #14:

score: 0

Accepted

time: 442ms

memory: 3512kb

input:

10000
2 3
0 2
38 61
50 55 35 52 17 40 15 51 39 11 5 41 2 33 49 25 0 24 53 13 30 59 9 34 57 37 38 27 29 1 19 31 46 8 45 58 6 42
11 17
5 13 1 11 2 0 6 7 4 12 10
6 11
3 0 4 7 10 6
21 29
17 14 7 18 20 28 23 25 16 3 22 5 21 2 0 9 13 1 12 11 19
5 5
0 3 2 1 4
20 23
19 16 0 1 15 18 14 12 21 6 22 8 11 13 20 ...

output:

result:

ok 20000 lines

Test #15:

score: 0

Accepted

time: 3114ms

memory: 3724kb

input:

10000
17 17
1 5 10 2 16 6 12 13 15 3 8 9 11 4 14 7 0
67 67
34 11 54 25 8 40 33 24 2 44 22 5 28 46 23 59 30 1 38 18 55 15 35 6 39 64 27 51 65 12 52 53 58 20 14 19 29 43 0 9 62 45 41 42 47 49 31 32 26 57 37 48 7 36 17 13 10 50 63 3 16 21 4 61 66 56 60
3 3
1 0 2
3 3
2 0 1
5 5
4 0 2 1 3
13 13
8 1 5 10 4...

output:

16 17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
66 67
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 
2 3
1 2 
2 3
1 2 
4 5
1 2 3 4 
12 13
1 2 3 4 5 6 7 8 9 10 ...

result:

ok 20000 lines

Test #16:

score: 0

Accepted

time: 187ms

memory: 3864kb

input:

1000
2 11
0 1
23 173
145 124 4 130 41 45 115 53 102 156 68 85 49 100 114 75 0 90 81 96 93 61 91
37 293
0 206 166 68 220 15 58 256 125 182 239 67 116 32 114 261 8 106 137 89 130 120 128 202 75 2 110 5 233 133 145 74 259 164 264 10 56
19 181
18 165 71 52 170 177 81 114 124 46 103 20 43 94 144 96 0 125...

output:

1 2
1 
2 3
50 60 
1 4
176 
18 2
27 38 42 44 45 51 52 58 66 80 94 100 122 127 147 148 171 172 
5 2
3 9 13 23 33 
1 3
126 
3 3
101 318 624 
1 3
16 
1 3
60 
8 2
8 10 24 31 32 38 39 44 
1 3
35 
8 2
17 19 24 44 51 59 61 69 
5 3
44 95 108 126 216 
6 3
82 100 284 471 479 501 
2 3
276 298 
5 3
72 181 186 19...

result:

ok 2000 lines

Test #17:

score: 0

Accepted

time: 297ms

memory: 3876kb

input:

1000
451 503
279 78 450 47 182 318 120 215 45 315 292 384 143 122 251 427 230 276 128 314 130 203 146 85 157 312 24 190 316 126 370 271 322 207 465 63 372 99 466 469 211 167 407 180 307 326 458 213 144 217 106 33 414 495 66 421 189 62 417 346 111 232 260 89 366 502 429 86 282 353 161 138 491 183 240...

output:

1 54
73 
1 45
97 
1 60
71 
1 41
53 
1 54
48 
1 50
15 
1 66
362 
1 27
22 
3 34
327 413 476 
1 22
20 
1 72
123 
1 62
137 
1 41
107 
1 40
34 
1 30
104 
1 49
151 
1 33
152 
1 40
6 
1 61
52 
2 3
1 2 
1 60
119 
1 48
288 
1 51
62 
1 12
7 
1 31
23 
1 37
38 
1 39
31 
1 70
79 
1 35
42 
1 43
55 
1 69
3 
1 59
2...

result:

ok 2000 lines

Test #18:

score: 0

Accepted

time: 169ms

memory: 3832kb

input:

1000
205 647
447 128 382 69 202 453 358 585 306 177 471 296 318 183 345 324 457 241 36 558 605 612 148 104 577 84 580 339 5 288 362 409 320 4 131 405 95 165 287 629 448 63 533 377 134 553 611 138 407 463 450 560 581 8 576 178 591 441 142 123 641 504 360 515 567 347 329 172 478 305 483 432 267 311 3 ...

output:

2 7
225 290 
3 7
7 27 54 
1 6
54 
1 4
17 
1 6
202 
1 5
71 
1 3
8 
1 7
98 
2 2
4 14 
4 4
12 36 57 102 
2 5
12 81 
2 4
1 117 
1 7
57 
2 5
30 47 
1 6
86 
9 3
13 19 21 28 34 66 72 87 96 
2 1
0 1 
1 9
114 
3 4
2 13 46 
2 4
16 108 
2 4
55 137 
2 4
12 13 
2 3
5 10 
1 5
3 
1 5
135 
1 6
157 
3 5
278 451 468 ...

result:

ok 2000 lines

Test #19:

score: 0

Accepted

time: 172ms

memory: 3480kb

input:

1000
94 193
184 174 163 185 118 147 125 21 155 93 188 36 112 10 95 101 64 128 179 35 48 43 42 150 108 23 31 104 3 120 2 78 84 53 25 69 116 97 71 0 59 98 83 160 85 90 117 121 61 102 30 191 19 135 56 29 55 173 24 15 47 89 16 161 154 114 124 146 109 144 111 182 14 183 60 74 140 148 157 138 170 115 86 6...

output:

1 12
131 
1 8
38 
1 6
14 
1 9
35 
5 3
5 8 10 25 31 
1 4
3 
1 10
247 
1 10
39 
1 11
495 
2 12
77 252 
1 12
662 
2 3
4 9 
1 10
528 
1 8
76 
1 10
177 
1 10
31 
2 11
159 185 
1 6
1 
1 13
162 
1 7
118 
2 7
98 147 
1 8
59 
1 8
56 
1 12
387 
1 7
3 
1 11
47 
1 8
64 
1 6
18 
4 6
23 38 100 131 
1 9
2 
1 8
21 ...

result:

ok 2000 lines

Test #20:

score: 0

Accepted

time: 196ms

memory: 3600kb

input:

1000
131 199
51 45 85 104 37 139 44 158 116 53 185 29 32 43 173 72 142 149 195 152 112 180 41 64 110 188 182 102 60 87 140 132 70 109 8 76 171 133 198 96 130 46 86 19 192 2 63 124 100 143 159 164 6 161 146 194 127 155 82 184 88 34 118 7 35 99 111 168 186 154 151 147 59 157 160 131 172 163 81 36 119 ...

output:

1 10
53 
1 17
11 
1 17
142 
1 19
40 
1 13
44 
2 8
32 36 
2 15
71 301 
2 17
295 327 
2 10
3 21 
1 19
30 
1 3
2 
1 18
767 
1 19
159 
1 8
7 
1 21
89 
1 14
223 
1 17
219 
1 26
176 
1 12
149 
1 13
24 
1 17
77 
4 4
8 12 13 17 
1 6
2 
1 15
263 
2 3
1 2 
3 13
30 36 45 
1 13
125 
4 15
282 474 554 557 
1 19
9...

result:

ok 2000 lines

Test #21:

score: -100

Time Limit Exceeded

input:

1000
139 139
44 102 101 91 113 62 65 127 137 18 103 42 53 10 52 87 4 89 78 70 55 132 123 121 83 5 8 29 58 100 71 34 33 106 138 3 110 43 59 117 107 32 82 22 14 30 47 77 73 133 72 97 21 86 6 49 9 90 126 23 19 80 41 85 26 61 75 125 122 105 15 60 88 135 56 46 79 94 63 129 17 98 74 13 16 108 112 96 39 7 ...

output:

138 139
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...