oj.uz

Submission #376068

# Submission time Handle Problem Language Result Execution time Memory
376068 2021-03-10T20:23:50 Z ijxjdjd Nice sequence (IZhO18_sequence) C++14
76 / 100
 159 ms 10016 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int T;
	cin >> T;
	FR(iter, T) {
        int N, M;
        cin >> N >> M;
        bool swapped = false;
        if (max(N,M)%min(N,M) == 0) {
            if (N >= M) {
                cout << N-1 << '\n';
                for (int i = 0; i < N-1; i++) {
                    cout << 1 << " ";
                }
                cout << '\n';
            }
            else {
                cout << M-1 << '\n';
                for (int i = 0; i < M-1; i++) {
                    cout << -1 << " ";
                }
                cout << '\n';
            }
        }
        else {
            if (N < M) {
                swap(N, M);
                swapped = true;
            }
            int d = N%M;
            int mx = N;
            while (d != 0) {
                mx = max(mx, d+N);
                d += N%M;
                if (d >= M) {
                    d -= M;
                }
                if (d == 0) {
                    break;
                }
            }
            vector<int> cntIn(mx, 0);
            vector<int> pref(mx, 0);
            for (int i = 0; i < mx; i++) {
                if (i+N < mx) {
                    cntIn[i+N]++;
                }
                if (i-M >= 0) {
                   cntIn[i-M]++;
                }
            }
            deque<int> deq;
            for (int i = 0; i < mx; i++) {
                if (cntIn[i] == 0) {
                   deq.push_back(i);
                   pref[i] = N*(deq.size()-1);
                }
            }
            while (deq.size()) {
                int i = deq.front();
                deq.pop_front();
                if (i+N<mx) {
                    cntIn[i+N]--;
                    pref[i+N] = max(pref[i+N], pref[i]+1);
                    if (cntIn[i+N] == 0) {
                        deq.push_back(i+N);
                    }
                }
                if (i-M>=0) {
                    cntIn[i-M]--;
                    pref[i-M] = max(pref[i-M], pref[i]+1);
                    if (cntIn[i-M] == 0) {
                        deq.push_back(i-M);
                    }
                }
            }
            for (int i = mx-1; i >=0; i--) {
                pref[i] -= pref[0];
            }
            if (!swapped) {
                for (int i = 1; i < mx; i++) {
                    pref[i] *= -1;
                }
            }
            cout << mx - 1 << '\n';
            for (int i = 1; i < mx; i++) {
                cout << pref[i] - pref[i-1] << " ";
            }
            cout << '\n';
        }
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 3 ms 364 KB Ok
7 Correct 12 ms 748 KB Ok
8 Correct 5 ms 492 KB Ok
9 Correct 11 ms 876 KB Ok
10 Correct 9 ms 620 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 89 ms 5716 KB Ok
7 Correct 97 ms 3616 KB Ok
8 Correct 142 ms 8148 KB Ok
9 Correct 108 ms 7416 KB Ok
10 Correct 66 ms 3896 KB Ok
11 Correct 101 ms 6936 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 1 ms 364 KB Ok
19 Correct 1 ms 364 KB Ok
20 Correct 1 ms 364 KB Ok
21 Correct 1 ms 364 KB Ok
22 Correct 1 ms 364 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 2 ms 492 KB Ok
25 Correct 2 ms 492 KB Ok
26 Correct 2 ms 492 KB Ok
27 Correct 2 ms 492 KB Ok
28 Correct 2 ms 364 KB Ok
29 Correct 2 ms 364 KB Ok
30 Correct 2 ms 364 KB Ok
31 Correct 2 ms 492 KB Ok
32 Correct 2 ms 492 KB Ok
33 Correct 2 ms 492 KB Ok
34 Correct 4 ms 620 KB Ok
35 Correct 6 ms 492 KB Ok
36 Correct 4 ms 492 KB Ok
37 Correct 4 ms 492 KB Ok
38 Correct 4 ms 492 KB Ok
39 Correct 4 ms 492 KB Ok
40 Correct 6 ms 492 KB Ok
41 Correct 5 ms 492 KB Ok
42 Correct 4 ms 492 KB Ok
43 Correct 4 ms 492 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 364 KB Ok
19 Correct 12 ms 748 KB Ok
20 Correct 5 ms 492 KB Ok
21 Correct 11 ms 876 KB Ok
22 Correct 9 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 2 ms 492 KB Ok
35 Correct 2 ms 492 KB Ok
36 Correct 2 ms 492 KB Ok
37 Correct 2 ms 492 KB Ok
38 Correct 2 ms 364 KB Ok
39 Correct 2 ms 364 KB Ok
40 Correct 2 ms 364 KB Ok
41 Correct 2 ms 492 KB Ok
42 Correct 2 ms 492 KB Ok
43 Correct 2 ms 492 KB Ok
44 Correct 4 ms 620 KB Ok
45 Correct 6 ms 492 KB Ok
46 Correct 4 ms 492 KB Ok
47 Correct 4 ms 492 KB Ok
48 Correct 4 ms 492 KB Ok
49 Correct 4 ms 492 KB Ok
50 Correct 6 ms 492 KB Ok
51 Correct 5 ms 492 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 4 ms 492 KB Ok
54 Correct 81 ms 5116 KB Ok
55 Correct 85 ms 5916 KB Ok
56 Correct 79 ms 5840 KB Ok
57 Correct 69 ms 4160 KB Ok
58 Correct 71 ms 5160 KB Ok
59 Correct 72 ms 4712 KB Ok
60 Correct 79 ms 4080 KB Ok
61 Correct 64 ms 4528 KB Ok
62 Correct 85 ms 6088 KB Ok
63 Correct 64 ms 4504 KB Ok
64 Correct 81 ms 5564 KB Ok
65 Correct 77 ms 5472 KB Ok
66 Correct 71 ms 4948 KB Ok
67 Correct 56 ms 3932 KB Ok
68 Correct 73 ms 4884 KB Ok
69 Correct 107 ms 7432 KB Ok
70 Correct 137 ms 7688 KB Ok
71 Correct 110 ms 7556 KB Ok
72 Correct 107 ms 7176 KB Ok
73 Correct 109 ms 7692 KB Ok
74 Correct 112 ms 7564 KB Ok
75 Correct 114 ms 7736 KB Ok
76 Correct 108 ms 7312 KB Ok
77 Correct 119 ms 7584 KB Ok
78 Correct 115 ms 7176 KB Ok
79 Correct 109 ms 7684 KB Ok
80 Correct 110 ms 7808 KB Ok
81 Correct 111 ms 7556 KB Ok
82 Correct 108 ms 7564 KB Ok
83 Correct 107 ms 7436 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 1 ms 364 KB Ok
15 Correct 1 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 3 ms 364 KB Ok
19 Correct 12 ms 748 KB Ok
20 Correct 5 ms 492 KB Ok
21 Correct 11 ms 876 KB Ok
22 Correct 9 ms 620 KB Ok
23 Correct 1 ms 364 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 1 ms 364 KB Ok
28 Correct 1 ms 364 KB Ok
29 Correct 1 ms 364 KB Ok
30 Correct 1 ms 364 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 1 ms 364 KB Ok
33 Correct 1 ms 364 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 1 ms 364 KB Ok
39 Correct 89 ms 5716 KB Ok
40 Correct 97 ms 3616 KB Ok
41 Correct 142 ms 8148 KB Ok
42 Correct 108 ms 7416 KB Ok
43 Correct 66 ms 3896 KB Ok
44 Correct 101 ms 6936 KB Ok
45 Correct 2 ms 492 KB Ok
46 Correct 2 ms 492 KB Ok
47 Correct 2 ms 492 KB Ok
48 Correct 2 ms 492 KB Ok
49 Correct 2 ms 364 KB Ok
50 Correct 2 ms 364 KB Ok
51 Correct 2 ms 364 KB Ok
52 Correct 2 ms 492 KB Ok
53 Correct 2 ms 492 KB Ok
54 Correct 2 ms 492 KB Ok
55 Correct 4 ms 620 KB Ok
56 Correct 6 ms 492 KB Ok
57 Correct 4 ms 492 KB Ok
58 Correct 4 ms 492 KB Ok
59 Correct 4 ms 492 KB Ok
60 Correct 4 ms 492 KB Ok
61 Correct 6 ms 492 KB Ok
62 Correct 5 ms 492 KB Ok
63 Correct 4 ms 492 KB Ok
64 Correct 4 ms 492 KB Ok
65 Correct 81 ms 5116 KB Ok
66 Correct 85 ms 5916 KB Ok
67 Correct 79 ms 5840 KB Ok
68 Correct 69 ms 4160 KB Ok
69 Correct 71 ms 5160 KB Ok
70 Correct 72 ms 4712 KB Ok
71 Correct 79 ms 4080 KB Ok
72 Correct 64 ms 4528 KB Ok
73 Correct 85 ms 6088 KB Ok
74 Correct 64 ms 4504 KB Ok
75 Correct 81 ms 5564 KB Ok
76 Correct 77 ms 5472 KB Ok
77 Correct 71 ms 4948 KB Ok
78 Correct 56 ms 3932 KB Ok
79 Correct 73 ms 4884 KB Ok
80 Correct 107 ms 7432 KB Ok
81 Correct 137 ms 7688 KB Ok
82 Correct 110 ms 7556 KB Ok
83 Correct 107 ms 7176 KB Ok
84 Correct 109 ms 7692 KB Ok
85 Correct 112 ms 7564 KB Ok
86 Correct 114 ms 7736 KB Ok
87 Correct 108 ms 7312 KB Ok
88 Correct 119 ms 7584 KB Ok
89 Correct 115 ms 7176 KB Ok
90 Correct 109 ms 7684 KB Ok
91 Correct 110 ms 7808 KB Ok
92 Correct 111 ms 7556 KB Ok
93 Correct 108 ms 7564 KB Ok
94 Correct 107 ms 7436 KB Ok
95 Incorrect 159 ms 10016 KB Absolute value of 1181262526 bigger than 1000000
96 Halted 0 ms 0 KB -