oj.uz

답안 #376082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376082 2021-03-10T20:32:30 Z ijxjdjd Nice sequence (IZhO18_sequence) C++14
29 / 100
 131 ms 6996 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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getrandom() {
    return uniform_int_distribution<int>(1, 1000)(rng);
}
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] = getrandom();
                }
            }
            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]+getrandom());
                    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]+getrandom());
                    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 2 ms 492 KB Ok
7 Correct 10 ms 876 KB Ok
8 Correct 5 ms 620 KB Ok
9 Correct 13 ms 1132 KB Ok
10 Correct 7 ms 748 KB Ok

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 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
0 / 15.0

# 결과 실행 시간 메모리 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 Incorrect 131 ms 6996 KB All the numbers must be nonzero
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 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 Incorrect 3 ms 512 KB All the numbers must be nonzero
25 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 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 2 ms 492 KB Ok
19 Correct 10 ms 876 KB Ok
20 Correct 5 ms 620 KB Ok
21 Correct 13 ms 1132 KB Ok
22 Correct 7 ms 748 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 Incorrect 3 ms 512 KB All the numbers must be nonzero
35 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 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 2 ms 492 KB Ok
19 Correct 10 ms 876 KB Ok
20 Correct 5 ms 620 KB Ok
21 Correct 13 ms 1132 KB Ok
22 Correct 7 ms 748 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 Incorrect 131 ms 6996 KB All the numbers must be nonzero
40 Halted 0 ms 0 KB -