oj.uz

Submission #376069

# Submission time Handle Problem Language Result Execution time Memory
376069 2021-03-10T20:25:55 Z ijxjdjd Nice sequence (IZhO18_sequence) C++14
58 / 100
 146 ms 7608 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] = rand()%10000;
                }
            }
            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 0 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 364 KB Ok
7 Correct 8 ms 748 KB Ok
8 Correct 4 ms 492 KB Ok
9 Correct 10 ms 876 KB Ok
10 Correct 6 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 83 ms 5460 KB Ok
7 Correct 67 ms 3616 KB Ok
8 Correct 146 ms 7608 KB Ok
9 Correct 106 ms 6904 KB Ok
10 Correct 63 ms 3512 KB Ok
11 Correct 104 ms 6424 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 3 ms 492 KB Ok
27 Correct 2 ms 364 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 5 ms 492 KB Ok
35 Correct 4 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 5 ms 492 KB Ok
41 Correct 4 ms 492 KB Ok
42 Correct 4 ms 512 KB Ok
43 Correct 4 ms 492 KB Ok

Subtask #6
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 0 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 2 ms 364 KB Ok
19 Correct 8 ms 748 KB Ok
20 Correct 4 ms 492 KB Ok
21 Correct 10 ms 876 KB Ok
22 Correct 6 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 3 ms 492 KB Ok
37 Correct 2 ms 364 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 5 ms 492 KB Ok
45 Correct 4 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 5 ms 492 KB Ok
51 Correct 4 ms 492 KB Ok
52 Correct 4 ms 512 KB Ok
53 Correct 4 ms 492 KB Ok
54 Incorrect 71 ms 4348 KB All the numbers must be nonzero
55 Halted 0 ms 0 KB -

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 0 ms 364 KB Ok
16 Correct 1 ms 364 KB Ok
17 Correct 1 ms 364 KB Ok
18 Correct 2 ms 364 KB Ok
19 Correct 8 ms 748 KB Ok
20 Correct 4 ms 492 KB Ok
21 Correct 10 ms 876 KB Ok
22 Correct 6 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 83 ms 5460 KB Ok
40 Correct 67 ms 3616 KB Ok
41 Correct 146 ms 7608 KB Ok
42 Correct 106 ms 6904 KB Ok
43 Correct 63 ms 3512 KB Ok
44 Correct 104 ms 6424 KB Ok
45 Correct 2 ms 492 KB Ok
46 Correct 2 ms 492 KB Ok
47 Correct 3 ms 492 KB Ok
48 Correct 2 ms 364 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 5 ms 492 KB Ok
56 Correct 4 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 5 ms 492 KB Ok
62 Correct 4 ms 492 KB Ok
63 Correct 4 ms 512 KB Ok
64 Correct 4 ms 492 KB Ok
65 Incorrect 71 ms 4348 KB All the numbers must be nonzero
66 Halted 0 ms 0 KB -