oj.uz

Submission #378888

# Submission time Handle Problem Language Result Execution time Memory
378888 2021-03-17T07:05:40 Z 2qbingxuan Nice sequence (IZhO18_sequence) C++14
100 / 100
 480 ms 31304 KB 
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#endif // local
#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;

        auto ok = [n, m](int L, bool out) {
            vector<int> indeg(L+1);
            for (int i = n; i <= L; i++)
                indeg[i-n] += 1;
            for (int i = m; i <= L; 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;
                if (int j = i-n; j >= 0)
                    if (--indeg[j] == 0)
                        q.push(j);
                if (int j = i+m; j <= L)
                    if (--indeg[j] == 0)
                        q.push(j);
            }
            for (int i = 0; i <= L; i++) if (indeg[i]) return false;
            if (out) {
                cout << L << '\n';
                for (int i = 1; i <= L; i++)
                    cout << vis[i] - vis[i-1] << (i==L ? '\n' : ' ');
            }
            return true;
        };
        /*
        int ans = 0;
        int s = 1;
        while (ok(s, false)) s <<= 1;
        for (; s; s >>= 1)
            if (ok(ans + s, false))
                ans += s;
                */
        debug(n + m - __gcd(n, m) - 1);
        ok(n+m-__gcd(n,m)-1, true);
    }
}

Compilation message

sequence.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      | 
sequence.cpp: In lambda function:
sequence.cpp:43:21: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   43 |                 if (int j = i-n; j >= 0)
      |                     ^~~
sequence.cpp:46:21: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   46 |                 if (int j = i+m; j <= L)
      |                     ^~~

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 0 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 364 KB Ok
7 Correct 9 ms 876 KB Ok
8 Correct 5 ms 492 KB Ok
9 Correct 13 ms 876 KB Ok
10 Correct 7 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 91 ms 4308 KB Ok
7 Correct 67 ms 3744 KB Ok
8 Correct 135 ms 6100 KB Ok
9 Correct 103 ms 6392 KB Ok
10 Correct 59 ms 2700 KB Ok
11 Correct 97 ms 5656 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 364 KB Ok
25 Correct 2 ms 364 KB Ok
26 Correct 3 ms 364 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 364 KB Ok
33 Correct 2 ms 364 KB Ok
34 Correct 4 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 4 ms 492 KB Ok
41 Correct 4 ms 492 KB Ok
42 Correct 4 ms 492 KB Ok
43 Correct 4 ms 640 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 0 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 364 KB Ok
19 Correct 9 ms 876 KB Ok
20 Correct 5 ms 492 KB Ok
21 Correct 13 ms 876 KB Ok
22 Correct 7 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 364 KB Ok
35 Correct 2 ms 364 KB Ok
36 Correct 3 ms 364 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 364 KB Ok
43 Correct 2 ms 364 KB Ok
44 Correct 4 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 4 ms 492 KB Ok
51 Correct 4 ms 492 KB Ok
52 Correct 4 ms 492 KB Ok
53 Correct 4 ms 640 KB Ok
54 Correct 68 ms 2592 KB Ok
55 Correct 73 ms 2760 KB Ok
56 Correct 73 ms 2640 KB Ok
57 Correct 56 ms 2080 KB Ok
58 Correct 67 ms 2340 KB Ok
59 Correct 68 ms 2356 KB Ok
60 Correct 58 ms 2336 KB Ok
61 Correct 57 ms 2320 KB Ok
62 Correct 76 ms 2648 KB Ok
63 Correct 72 ms 2348 KB Ok
64 Correct 72 ms 2724 KB Ok
65 Correct 69 ms 2576 KB Ok
66 Correct 68 ms 2556 KB Ok
67 Correct 56 ms 2268 KB Ok
68 Correct 81 ms 2320 KB Ok
69 Correct 107 ms 6536 KB Ok
70 Correct 110 ms 7688 KB Ok
71 Correct 124 ms 5764 KB Ok
72 Correct 108 ms 6792 KB Ok
73 Correct 108 ms 6204 KB Ok
74 Correct 102 ms 5132 KB Ok
75 Correct 103 ms 5384 KB Ok
76 Correct 107 ms 7440 KB Ok
77 Correct 103 ms 4744 KB Ok
78 Correct 110 ms 7176 KB Ok
79 Correct 108 ms 6532 KB Ok
80 Correct 105 ms 6420 KB Ok
81 Correct 108 ms 6788 KB Ok
82 Correct 110 ms 6412 KB Ok
83 Correct 105 ms 5260 KB Ok

Subtask #7
24.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 0 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 364 KB Ok
19 Correct 9 ms 876 KB Ok
20 Correct 5 ms 492 KB Ok
21 Correct 13 ms 876 KB Ok
22 Correct 7 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 91 ms 4308 KB Ok
40 Correct 67 ms 3744 KB Ok
41 Correct 135 ms 6100 KB Ok
42 Correct 103 ms 6392 KB Ok
43 Correct 59 ms 2700 KB Ok
44 Correct 97 ms 5656 KB Ok
45 Correct 2 ms 364 KB Ok
46 Correct 2 ms 364 KB Ok
47 Correct 3 ms 364 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 364 KB Ok
54 Correct 2 ms 364 KB Ok
55 Correct 4 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 4 ms 492 KB Ok
62 Correct 4 ms 492 KB Ok
63 Correct 4 ms 492 KB Ok
64 Correct 4 ms 640 KB Ok
65 Correct 68 ms 2592 KB Ok
66 Correct 73 ms 2760 KB Ok
67 Correct 73 ms 2640 KB Ok
68 Correct 56 ms 2080 KB Ok
69 Correct 67 ms 2340 KB Ok
70 Correct 68 ms 2356 KB Ok
71 Correct 58 ms 2336 KB Ok
72 Correct 57 ms 2320 KB Ok
73 Correct 76 ms 2648 KB Ok
74 Correct 72 ms 2348 KB Ok
75 Correct 72 ms 2724 KB Ok
76 Correct 69 ms 2576 KB Ok
77 Correct 68 ms 2556 KB Ok
78 Correct 56 ms 2268 KB Ok
79 Correct 81 ms 2320 KB Ok
80 Correct 107 ms 6536 KB Ok
81 Correct 110 ms 7688 KB Ok
82 Correct 124 ms 5764 KB Ok
83 Correct 108 ms 6792 KB Ok
84 Correct 108 ms 6204 KB Ok
85 Correct 102 ms 5132 KB Ok
86 Correct 103 ms 5384 KB Ok
87 Correct 107 ms 7440 KB Ok
88 Correct 103 ms 4744 KB Ok
89 Correct 110 ms 7176 KB Ok
90 Correct 108 ms 6532 KB Ok
91 Correct 105 ms 6420 KB Ok
92 Correct 108 ms 6788 KB Ok
93 Correct 110 ms 6412 KB Ok
94 Correct 105 ms 5260 KB Ok
95 Correct 160 ms 6432 KB Ok
96 Correct 232 ms 9628 KB Ok
97 Correct 244 ms 8400 KB Ok
98 Correct 208 ms 6604 KB Ok
99 Correct 251 ms 7472 KB Ok
100 Correct 208 ms 7004 KB Ok
101 Correct 213 ms 8252 KB Ok
102 Correct 203 ms 8432 KB Ok
103 Correct 200 ms 7320 KB Ok
104 Correct 238 ms 7704 KB Ok
105 Correct 229 ms 8036 KB Ok
106 Correct 191 ms 7088 KB Ok
107 Correct 221 ms 7212 KB Ok
108 Correct 239 ms 8464 KB Ok
109 Correct 217 ms 8048 KB Ok
110 Correct 448 ms 21424 KB Ok
111 Correct 466 ms 31212 KB Ok
112 Correct 443 ms 23528 KB Ok
113 Correct 480 ms 27600 KB Ok
114 Correct 446 ms 29240 KB Ok
115 Correct 448 ms 28340 KB Ok
116 Correct 446 ms 27948 KB Ok
117 Correct 440 ms 29132 KB Ok
118 Correct 441 ms 24660 KB Ok
119 Correct 461 ms 30120 KB Ok
120 Correct 437 ms 24804 KB Ok
121 Correct 442 ms 23564 KB Ok
122 Correct 442 ms 26576 KB Ok
123 Correct 453 ms 31304 KB Ok
124 Correct 464 ms 20280 KB Ok
125 Correct 390 ms 13520 KB Ok