QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311160#508. Nice sequencejasper16624 307ms17616kbC++171.7kb2024-01-22 00:12:492024-01-22 00:12:50

Judging History

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

  • [2024-01-22 00:12:50]
  • 评测
  • 测评结果:24
  • 用时:307ms
  • 内存:17616kb
  • [2024-01-22 00:12:49]
  • 提交

answer

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;
int n, m;
vector <int> adj[N];
int deg[N], a[N];

bool check(int k) {
    for (int i = 0; i <= k; ++i) {
        if (i + m <= k) {
            adj[i].push_back(i + m);
            deg[i + m]++;
        }
        if (i >= n) {
            adj[i].push_back(i - n);
            deg[i - n]++;
        }
    }

    queue <int> q;
    for (int i = 0; i <= k; ++i)
        if (deg[i] == 0)
            q.push(i);

    int cnt = 0;
    vector <int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        a[u] = ++cnt;
        for (int v : adj[u]) {
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }
    for (int i = 0; i <= k; ++i) {
        adj[i].clear();
        deg[i] = 0;
    }
    // if the graph is cyclic then no topo order exists
    return ((int) topo.size() == k + 1);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int T; 
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int l = 1, r = 2 * (m + n - 1);
        int ans = -1;
//        debug(check(3));
        while (l <= r) {
            int mi = (l + r) / 2;
            if (check(mi)) {
                ans = mi;
                l = mi + 1;
            }
            else 
                r = mi - 1;
        } 
        check(ans);
        cout << ans << "\n";
        for (int i = 1; i <= ans; ++i) {
            cout << (a[i] - a[i - 1]) << " \n"[i == ans];
        }   
    }
}



详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 8228kb

input:

3
3 1
2 3
1 1

output:

2
1 1
3
2 -3 2
-1

result:

wrong answer Jury has the better answer : jans = 0, pans = -1

Subtask #2:

score: 9
Accepted

Test #14:

score: 9
Accepted
time: 0ms
memory: 8736kb

input:

10
2 2
3 2
4 2
5 2
2 6
2 7
2 8
9 2
10 2
2 11

output:

1
1
3
-2 3 -2
3
1 1 1
5
-3 4 -3 4 -3
5
1 -3 1 -3 1
7
4 -5 4 -5 4 -5 4
7
1 -3 1 -3 1 -3 1
9
-5 6 -5 6 -5 6 -5 6 -5
9
1 1 1 1 1 1 1 1 1
11
6 -7 6 -7 6 -7 6 -7 6 -7 6

result:

ok Ok

Test #15:

score: 0
Accepted
time: 2ms
memory: 8224kb

input:

10
12 2
2 13
14 2
2 15
2 16
17 2
18 2
19 2
20 2
21 2

output:

11
1 1 1 1 1 1 1 1 1 1 1
13
7 -8 7 -8 7 -8 7 -8 7 -8 7 -8 7
13
1 1 1 1 1 1 1 1 1 1 1 1 1
15
8 -9 8 -9 8 -9 8 -9 8 -9 8 -9 8 -9 8
15
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1
17
-9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9
17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19
-10 11 -10 11 -10 11 -10 11 -10 11 -1...

result:

ok Ok

Test #16:

score: 0
Accepted
time: 2ms
memory: 9860kb

input:

10
2 22
2 23
2 24
2 25
26 2
2 27
28 2
2 29
30 2
31 2

output:

21
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1
23
12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12
23
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1
25
13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13
25
1 1 1 1 1...

result:

ok Ok

Test #17:

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

input:

10
32 2
2 33
34 2
35 2
2 36
2 37
2 38
39 2
40 2
41 2

output:

31
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 1 1 1 1 1 1
33
17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17
33
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 1 1 1 1 1 1 1 1
35
-18 19 -18 19 -18 19 -18 19 -18 19 -18 19 -18...

result:

ok Ok

Test #18:

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

input:

10
2 42
43 2
2 44
45 2
46 2
2 47
48 2
2 49
50 2
2 51

output:

41
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1
43
-22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22
43
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -...

result:

ok Ok

Test #19:

score: 0
Accepted
time: 5ms
memory: 9292kb

input:

10
2 1727
1728 2
1729 2
1730 2
1731 2
1732 2
2 1733
2 1734
2 1735
2 1736

output:

1727
864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -86...

result:

ok Ok

Test #20:

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

input:

10
2 8495
2 8496
2 8497
2 8498
8499 2
8500 2
2 8501
8502 2
8503 2
2 8504

output:

8495
4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -424...

result:

ok Ok

Test #21:

score: 0
Accepted
time: 4ms
memory: 9756kb

input:

10
2 3989
2 3990
2 3991
2 3992
2 3993
3994 2
3995 2
3996 2
2 3997
2 3998

output:

3989
1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -199...

result:

ok Ok

Test #22:

score: 0
Accepted
time: 17ms
memory: 8784kb

input:

10
9991 2
2 9992
2 9993
9994 2
9995 2
2 9996
2 9997
9998 2
9999 2
10000 2

output:

9991
-4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 499...

result:

ok Ok

Test #23:

score: 0
Accepted
time: 6ms
memory: 8588kb

input:

10
2 5682
5683 2
5684 2
2 5685
2 5686
5687 2
2 5688
2 5689
2 5690
2 5691

output:

5681
1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 ...

result:

ok Ok

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 2ms
memory: 9076kb

input:

10
7 1
1 5
1 1
10 1
1 4
3 1
1 6
1 2
1 9
8 1

output:

6
1 1 1 1 1 1
4
-1 -1 -1 -1
-1
9
1 1 1 1 1 1 1 1 1
3
-1 -1 -1
2
1 1
5
-1 -1 -1 -1 -1
1
-1
8
-1 -1 -1 -1 -1 -1 -1 -1
7
1 1 1 1 1 1 1

result:

wrong answer Jury has the better answer : jans = 0, pans = -1

Subtask #4:

score: 15
Accepted

Test #34:

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

input:

10
2 3
2 4
4 3
5 3
5 4
6 4
6 5
5 7
7 6
6 8

output:

3
2 -3 2
3
1 -3 1
5
-2 -2 5 -2 -2
6
3 -5 3 3 -5 3
7
-2 -2 -2 7 -2 -2 -2
7
1 -5 1 5 1 -5 1
9
-2 -2 -2 -2 9 -2 -2 -2 -2
10
-5 7 -5 7 -5 -5 7 -5 7 -5
11
-2 -2 -2 -2 -2 11 -2 -2 -2 -2 -2
11
1 3 1 3 1 -11 1 3 1 3 1

result:

ok Ok

Test #35:

score: 0
Accepted
time: 2ms
memory: 8872kb

input:

10
8 7
7 9
8 9
8 10
10 9
11 9
11 10
10 12
12 11
13 11

output:

13
-2 -2 -2 -2 -2 -2 13 -2 -2 -2 -2 -2 -2
14
-7 9 -7 9 -7 9 -7 -7 9 -7 9 -7 9 -7
15
2 2 2 2 2 2 2 -15 2 2 2 2 2 2 2
15
1 3 1 3 1 3 1 -15 1 3 1 3 1 3 1
17
-2 -2 -2 -2 -2 -2 -2 -2 17 -2 -2 -2 -2 -2 -2 -2 -2
18
9 -11 9 -11 9 -11 9 -11 9 9 -11 9 -11 9 -11 9 -11 9
19
-2 -2 -2 -2 -2 -2 -2 -2 -2 19 -2 -2 -...

result:

ok Ok

Test #36:

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

input:

10
13 12
14 12
14 13
15 13
15 14
14 16
15 16
17 15
17 16
16 18

output:

23
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 23 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
23
1 -5 1 -5 1 -5 1 -5 1 -5 1 21 1 -5 1 -5 1 -5 1 -5 1 -5 1
25
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 25 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
26
13 -15 13 -15 13 -15 13 -15 13 -15 13 -15 13 13 -15 13 -15 13 -15 13 -15 13 -15 13 -15 ...

result:

ok Ok

Test #37:

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

input:

10
18 17
17 19
18 19
18 20
20 19
21 19
21 20
20 22
21 22
21 23

output:

33
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 33 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
34
-17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17
35
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -35 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
...

result:

ok Ok

Test #38:

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

input:

10
23 22
22 24
23 24
25 23
24 25
26 24
26 25
25 27
27 26
26 28

output:

43
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 43 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
43
1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 -43 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1
45
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -45 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

result:

ok Ok

Test #39:

score: 0
Accepted
time: 170ms
memory: 16824kb

input:

10
83402 83404
52908 52906
74520 74521
24222 24221
1082 1083
8982 8980
10142 10141
34908 34906
58179 58181
50841 50843

output:

166803
1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1...

result:

ok Ok

Test #40:

score: 0
Accepted
time: 180ms
memory: 17544kb

input:

10
20084 20083
10333 10331
98649 98648
72803 72804
40654 40655
1612 1614
26871 26873
5060 5062
60616 60615
6832 6830

output:

40165
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...

result:

ok Ok

Test #41:

score: 0
Accepted
time: 307ms
memory: 17616kb

input:

10
79524 79523
91096 91095
90747 90749
83462 83460
78387 78388
67918 67920
1682 1681
13180 13179
98702 98700
70766 70767

output:

159045
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2...

result:

ok Ok

Test #42:

score: 0
Accepted
time: 207ms
memory: 16416kb

input:

10
18052 18051
55715 55717
57933 57931
78574 78576
37241 37243
4851 4853
83373 83375
37863 37865
37892 37894
83822 83821

output:

36101
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...

result:

ok Ok

Test #43:

score: 0
Accepted
time: 134ms
memory: 13936kb

input:

10
2394 2392
24337 24339
55254 55256
46338 46339
11158 11159
20181 20182
59816 59818
15018 15020
39382 39381
33622 33623

output:

4783
1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 ...

result:

ok Ok

Test #44:

score: 0
Accepted
time: 187ms
memory: 17568kb

input:

10
13518 13517
67574 67576
76936 76938
73347 73349
7000 7001
19392 19391
6627 6626
24433 24432
98264 98265
94139 94141

output:

27033
-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...

result:

ok Ok

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%