oj.uz

Submission #378878

# Submission time Handle Problem Language Result Execution time Memory
378878 2021-03-17T06:54:09 Z 2qbingxuan Nice sequence (IZhO18_sequence) C++14
61 / 100
 2000 ms 21084 KB 
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#define pb emplace_back
#define all(v) begin(v),end(v)

using namespace std;
typedef int64_t ll;

constexpr ll maxn = 300025, INF = 1e18, MOD = 998244353, K = 14699, inf = 1e9;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> jizz;
        auto ok = [n, m, &jizz](int L) {
            vector<vector<int>> g(L+1);
            vector<int> indeg(L+1);
            for (int i = n; i <= L; i++)
                g[i].push_back(i-n), indeg[i-n] += 1;
            for (int i = m; i <= L; i++)
                g[i-m].push_back(i), indeg[i] += 1;
            queue<int> q;
            for (int i = 0; i <= L; i++) if (indeg[i] == 0) q.push(i);
            vector<int> vis(L+1);
            int cur = 0;
            while (!q.empty()) {
                int i = q.front(); q.pop();
                vis[i] = ++cur;
                for (int j: g[i]) if (--indeg[j] == 0) q.push(j);
            }
            for (int i = 0; i <= L; i++) if (indeg[i]) return false;
            jizz = vis;
            return true;
        };
        int ans = 0;
        int s = 1;
        while (ok(s)) s <<= 1;
        for (; s; s >>= 1)
            if (ok(ans + s))
                ans += s;
        ok(ans);
        cout << ans << '\n';
        for (int i = 1; i <= ans; i++)
            cout << jizz[i] - jizz[i-1] << (i==ans ? '\n' : ' ');
    }
}

Compilation message

sequence.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      |

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 20 ms 492 KB Ok
7 Correct 143 ms 1856 KB Ok
8 Correct 43 ms 808 KB Ok
9 Correct 137 ms 1824 KB Ok
10 Correct 70 ms 1192 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
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 384 KB Ok
6 Correct 1161 ms 20352 KB Ok
7 Correct 991 ms 19004 KB Ok
8 Execution timed out 2029 ms 21084 KB Time limit exceeded
9 Halted 0 ms 0 KB -

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 16 ms 636 KB Ok
25 Correct 16 ms 656 KB Ok
26 Correct 17 ms 692 KB Ok
27 Correct 14 ms 632 KB Ok
28 Correct 13 ms 668 KB Ok
29 Correct 10 ms 492 KB Ok
30 Correct 12 ms 620 KB Ok
31 Correct 17 ms 680 KB Ok
32 Correct 18 ms 648 KB Ok
33 Correct 16 ms 664 KB Ok
34 Correct 36 ms 744 KB Ok
35 Correct 34 ms 784 KB Ok
36 Correct 35 ms 792 KB Ok
37 Correct 35 ms 768 KB Ok
38 Correct 33 ms 784 KB Ok
39 Correct 35 ms 756 KB Ok
40 Correct 37 ms 792 KB Ok
41 Correct 35 ms 836 KB Ok
42 Correct 36 ms 752 KB Ok
43 Correct 36 ms 808 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 20 ms 492 KB Ok
19 Correct 143 ms 1856 KB Ok
20 Correct 43 ms 808 KB Ok
21 Correct 137 ms 1824 KB Ok
22 Correct 70 ms 1192 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 16 ms 636 KB Ok
35 Correct 16 ms 656 KB Ok
36 Correct 17 ms 692 KB Ok
37 Correct 14 ms 632 KB Ok
38 Correct 13 ms 668 KB Ok
39 Correct 10 ms 492 KB Ok
40 Correct 12 ms 620 KB Ok
41 Correct 17 ms 680 KB Ok
42 Correct 18 ms 648 KB Ok
43 Correct 16 ms 664 KB Ok
44 Correct 36 ms 744 KB Ok
45 Correct 34 ms 784 KB Ok
46 Correct 35 ms 792 KB Ok
47 Correct 35 ms 768 KB Ok
48 Correct 33 ms 784 KB Ok
49 Correct 35 ms 756 KB Ok
50 Correct 37 ms 792 KB Ok
51 Correct 35 ms 836 KB Ok
52 Correct 36 ms 752 KB Ok
53 Correct 36 ms 808 KB Ok
54 Correct 836 ms 10640 KB Ok
55 Correct 1092 ms 10836 KB Ok
56 Correct 1022 ms 11104 KB Ok
57 Correct 708 ms 10244 KB Ok
58 Correct 916 ms 10536 KB Ok
59 Correct 864 ms 10792 KB Ok
60 Correct 706 ms 10128 KB Ok
61 Correct 723 ms 10164 KB Ok
62 Correct 1151 ms 11072 KB Ok
63 Correct 802 ms 10120 KB Ok
64 Correct 1112 ms 10808 KB Ok
65 Correct 1014 ms 10396 KB Ok
66 Correct 829 ms 10208 KB Ok
67 Correct 675 ms 9792 KB Ok
68 Correct 915 ms 10500 KB Ok
69 Correct 1777 ms 15128 KB Ok
70 Correct 1666 ms 16452 KB Ok
71 Correct 1714 ms 14504 KB Ok
72 Correct 1820 ms 15040 KB Ok
73 Correct 1741 ms 14912 KB Ok
74 Correct 1607 ms 13640 KB Ok
75 Correct 1930 ms 14084 KB Ok
76 Correct 1794 ms 15152 KB Ok
77 Correct 1665 ms 13680 KB Ok
78 Correct 1733 ms 16176 KB Ok
79 Correct 1792 ms 15324 KB Ok
80 Correct 1634 ms 15108 KB Ok
81 Correct 1745 ms 16264 KB Ok
82 Correct 1623 ms 14368 KB Ok
83 Correct 1771 ms 13116 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 20 ms 492 KB Ok
19 Correct 143 ms 1856 KB Ok
20 Correct 43 ms 808 KB Ok
21 Correct 137 ms 1824 KB Ok
22 Correct 70 ms 1192 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 384 KB Ok
39 Correct 1161 ms 20352 KB Ok
40 Correct 991 ms 19004 KB Ok
41 Execution timed out 2029 ms 21084 KB Time limit exceeded
42 Halted 0 ms 0 KB -