# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
173801 | 2020-01-05T12:43:58 Z | davitmarg | Nice sequence (IZhO18_sequence) | C++17 | 2000 ms | 50196 KB |
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() using namespace std; const int N = 200005; int gcd(int a, int b) { if (!a || !b) return a + b; return gcd(b, a % b); } LL lca(LL a, LL b) { return a * b / gcd(a, b); } int q, n, m, k; vector<int> t, a, used, tin; vector<vector<int>> g; inline void dfs(int v) { used[v] = 1; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (used[to]) continue; dfs(to); } tin[v] = -t.size(); t.PB(v); } bool check(int x) { t.clear(); a.resize(x + 2); used.resize(x + 2); tin.resize(x + 2); g.resize(x + 2); for (int i = 0; i <= x; i++) { g[i].clear(); used[i] = 0; a[i] = i; } for (int i = 0; i <= x; i++) { if (i - m >= 0) g[i - m].PB(i); if (i + n <= x) g[i + n].PB(i); } for (int i = 0; i <= x; i++) if (!used[i]) dfs(i); reverse(all(t)); //cout << "!!!!!" << x << endl; for (int i = 0; i < t.size(); i++) { int v = t[i]; for (int j = 0; j < g[v].size(); j++) { int to = g[v][j]; if (tin[to] <= tin[v]) return 0; //cout << v << " : " << to << endl; a[to] = max(a[to], a[v] + 1); } } return 1; } int main() { cin >> q; while (q--) { k = 0; cin >> n >> m; LL l, r, mid; l = 0; // r = min(lca(n, m) - 1ll, 400000ll); // while (l <= r) // { // mid = (l + r) / 2; // if (check(mid)) // { // k = mid; // l = mid + 1; // } // else // r = mid - 1; // } k = n + m - gcd(n, m) - 1; check(k); cout << k << endl; for (int i = 1; i <= k; i++) printf("%d ", a[i] - a[i - 1]); cout << endl; } return 0; } /* 4 3 1 2 3 1 1 2 2 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 380 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 2 ms | 376 KB | Ok |
7 | Correct | 2 ms | 376 KB | Ok |
8 | Correct | 3 ms | 376 KB | Ok |
9 | Correct | 2 ms | 376 KB | Ok |
10 | Correct | 2 ms | 256 KB | Ok |
11 | Correct | 2 ms | 256 KB | Ok |
12 | Correct | 2 ms | 376 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 376 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 376 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 4 ms | 504 KB | Ok |
7 | Correct | 13 ms | 1456 KB | Ok |
8 | Correct | 7 ms | 888 KB | Ok |
9 | Correct | 16 ms | 1676 KB | Ok |
10 | Correct | 10 ms | 1136 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 4 ms | 504 KB | Ok |
3 | Correct | 2 ms | 256 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 2 ms | 380 KB | Ok |
7 | Correct | 2 ms | 376 KB | Ok |
8 | Correct | 2 ms | 376 KB | Ok |
9 | Correct | 2 ms | 256 KB | Ok |
10 | Correct | 2 ms | 376 KB | Ok |
11 | Correct | 2 ms | 376 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 256 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 256 KB | Ok |
6 | Correct | 131 ms | 17748 KB | Ok |
7 | Correct | 115 ms | 19552 KB | Ok |
8 | Correct | 203 ms | 21216 KB | Ok |
9 | Correct | 166 ms | 18596 KB | Ok |
10 | Correct | 104 ms | 12192 KB | Ok |
11 | Correct | 165 ms | 21604 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 380 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 2 ms | 376 KB | Ok |
7 | Correct | 2 ms | 376 KB | Ok |
8 | Correct | 3 ms | 376 KB | Ok |
9 | Correct | 2 ms | 376 KB | Ok |
10 | Correct | 2 ms | 256 KB | Ok |
11 | Correct | 2 ms | 256 KB | Ok |
12 | Correct | 2 ms | 376 KB | Ok |
13 | Correct | 2 ms | 256 KB | Ok |
14 | Correct | 4 ms | 504 KB | Ok |
15 | Correct | 2 ms | 256 KB | Ok |
16 | Correct | 2 ms | 256 KB | Ok |
17 | Correct | 2 ms | 376 KB | Ok |
18 | Correct | 2 ms | 380 KB | Ok |
19 | Correct | 2 ms | 376 KB | Ok |
20 | Correct | 2 ms | 376 KB | Ok |
21 | Correct | 2 ms | 256 KB | Ok |
22 | Correct | 2 ms | 376 KB | Ok |
23 | Correct | 2 ms | 376 KB | Ok |
24 | Correct | 4 ms | 632 KB | Ok |
25 | Correct | 4 ms | 632 KB | Ok |
26 | Correct | 4 ms | 632 KB | Ok |
27 | Correct | 4 ms | 504 KB | Ok |
28 | Correct | 4 ms | 504 KB | Ok |
29 | Correct | 4 ms | 504 KB | Ok |
30 | Correct | 4 ms | 504 KB | Ok |
31 | Correct | 4 ms | 632 KB | Ok |
32 | Correct | 5 ms | 604 KB | Ok |
33 | Correct | 4 ms | 632 KB | Ok |
34 | Correct | 7 ms | 888 KB | Ok |
35 | Correct | 7 ms | 888 KB | Ok |
36 | Correct | 8 ms | 888 KB | Ok |
37 | Correct | 8 ms | 888 KB | Ok |
38 | Correct | 8 ms | 888 KB | Ok |
39 | Correct | 7 ms | 760 KB | Ok |
40 | Correct | 8 ms | 888 KB | Ok |
41 | Correct | 7 ms | 764 KB | Ok |
42 | Correct | 8 ms | 760 KB | Ok |
43 | Correct | 8 ms | 888 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 380 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 2 ms | 376 KB | Ok |
7 | Correct | 2 ms | 376 KB | Ok |
8 | Correct | 3 ms | 376 KB | Ok |
9 | Correct | 2 ms | 376 KB | Ok |
10 | Correct | 2 ms | 256 KB | Ok |
11 | Correct | 2 ms | 256 KB | Ok |
12 | Correct | 2 ms | 376 KB | Ok |
13 | Correct | 2 ms | 256 KB | Ok |
14 | Correct | 2 ms | 376 KB | Ok |
15 | Correct | 2 ms | 376 KB | Ok |
16 | Correct | 2 ms | 376 KB | Ok |
17 | Correct | 2 ms | 376 KB | Ok |
18 | Correct | 4 ms | 504 KB | Ok |
19 | Correct | 13 ms | 1456 KB | Ok |
20 | Correct | 7 ms | 888 KB | Ok |
21 | Correct | 16 ms | 1676 KB | Ok |
22 | Correct | 10 ms | 1136 KB | Ok |
23 | Correct | 2 ms | 256 KB | Ok |
24 | Correct | 4 ms | 504 KB | Ok |
25 | Correct | 2 ms | 256 KB | Ok |
26 | Correct | 2 ms | 256 KB | Ok |
27 | Correct | 2 ms | 376 KB | Ok |
28 | Correct | 2 ms | 380 KB | Ok |
29 | Correct | 2 ms | 376 KB | Ok |
30 | Correct | 2 ms | 376 KB | Ok |
31 | Correct | 2 ms | 256 KB | Ok |
32 | Correct | 2 ms | 376 KB | Ok |
33 | Correct | 2 ms | 376 KB | Ok |
34 | Correct | 4 ms | 632 KB | Ok |
35 | Correct | 4 ms | 632 KB | Ok |
36 | Correct | 4 ms | 632 KB | Ok |
37 | Correct | 4 ms | 504 KB | Ok |
38 | Correct | 4 ms | 504 KB | Ok |
39 | Correct | 4 ms | 504 KB | Ok |
40 | Correct | 4 ms | 504 KB | Ok |
41 | Correct | 4 ms | 632 KB | Ok |
42 | Correct | 5 ms | 604 KB | Ok |
43 | Correct | 4 ms | 632 KB | Ok |
44 | Correct | 7 ms | 888 KB | Ok |
45 | Correct | 7 ms | 888 KB | Ok |
46 | Correct | 8 ms | 888 KB | Ok |
47 | Correct | 8 ms | 888 KB | Ok |
48 | Correct | 8 ms | 888 KB | Ok |
49 | Correct | 7 ms | 760 KB | Ok |
50 | Correct | 8 ms | 888 KB | Ok |
51 | Correct | 7 ms | 764 KB | Ok |
52 | Correct | 8 ms | 760 KB | Ok |
53 | Correct | 8 ms | 888 KB | Ok |
54 | Correct | 100 ms | 9000 KB | Ok |
55 | Correct | 115 ms | 8388 KB | Ok |
56 | Correct | 111 ms | 8592 KB | Ok |
57 | Correct | 84 ms | 7444 KB | Ok |
58 | Correct | 120 ms | 8880 KB | Ok |
59 | Correct | 105 ms | 7764 KB | Ok |
60 | Correct | 91 ms | 7404 KB | Ok |
61 | Correct | 91 ms | 8588 KB | Ok |
62 | Correct | 123 ms | 8496 KB | Ok |
63 | Correct | 95 ms | 7364 KB | Ok |
64 | Correct | 137 ms | 8324 KB | Ok |
65 | Correct | 111 ms | 8504 KB | Ok |
66 | Correct | 95 ms | 7960 KB | Ok |
67 | Correct | 86 ms | 8112 KB | Ok |
68 | Correct | 104 ms | 8164 KB | Ok |
69 | Correct | 278 ms | 14516 KB | Ok |
70 | Correct | 402 ms | 15676 KB | Ok |
71 | Correct | 331 ms | 12852 KB | Ok |
72 | Correct | 326 ms | 15028 KB | Ok |
73 | Correct | 339 ms | 13492 KB | Ok |
74 | Correct | 298 ms | 12856 KB | Ok |
75 | Correct | 329 ms | 13172 KB | Ok |
76 | Correct | 374 ms | 15544 KB | Ok |
77 | Correct | 318 ms | 12424 KB | Ok |
78 | Correct | 338 ms | 15312 KB | Ok |
79 | Correct | 375 ms | 14400 KB | Ok |
80 | Correct | 292 ms | 13628 KB | Ok |
81 | Correct | 307 ms | 14800 KB | Ok |
82 | Correct | 307 ms | 14256 KB | Ok |
83 | Correct | 315 ms | 13492 KB | Ok |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Ok |
2 | Correct | 2 ms | 380 KB | Ok |
3 | Correct | 2 ms | 376 KB | Ok |
4 | Correct | 2 ms | 256 KB | Ok |
5 | Correct | 2 ms | 376 KB | Ok |
6 | Correct | 2 ms | 376 KB | Ok |
7 | Correct | 2 ms | 376 KB | Ok |
8 | Correct | 3 ms | 376 KB | Ok |
9 | Correct | 2 ms | 376 KB | Ok |
10 | Correct | 2 ms | 256 KB | Ok |
11 | Correct | 2 ms | 256 KB | Ok |
12 | Correct | 2 ms | 376 KB | Ok |
13 | Correct | 2 ms | 256 KB | Ok |
14 | Correct | 2 ms | 376 KB | Ok |
15 | Correct | 2 ms | 376 KB | Ok |
16 | Correct | 2 ms | 376 KB | Ok |
17 | Correct | 2 ms | 376 KB | Ok |
18 | Correct | 4 ms | 504 KB | Ok |
19 | Correct | 13 ms | 1456 KB | Ok |
20 | Correct | 7 ms | 888 KB | Ok |
21 | Correct | 16 ms | 1676 KB | Ok |
22 | Correct | 10 ms | 1136 KB | Ok |
23 | Correct | 2 ms | 256 KB | Ok |
24 | Correct | 4 ms | 504 KB | Ok |
25 | Correct | 2 ms | 256 KB | Ok |
26 | Correct | 2 ms | 256 KB | Ok |
27 | Correct | 2 ms | 376 KB | Ok |
28 | Correct | 2 ms | 380 KB | Ok |
29 | Correct | 2 ms | 376 KB | Ok |
30 | Correct | 2 ms | 376 KB | Ok |
31 | Correct | 2 ms | 256 KB | Ok |
32 | Correct | 2 ms | 376 KB | Ok |
33 | Correct | 2 ms | 376 KB | Ok |
34 | Correct | 2 ms | 256 KB | Ok |
35 | Correct | 2 ms | 256 KB | Ok |
36 | Correct | 2 ms | 376 KB | Ok |
37 | Correct | 2 ms | 256 KB | Ok |
38 | Correct | 2 ms | 256 KB | Ok |
39 | Correct | 131 ms | 17748 KB | Ok |
40 | Correct | 115 ms | 19552 KB | Ok |
41 | Correct | 203 ms | 21216 KB | Ok |
42 | Correct | 166 ms | 18596 KB | Ok |
43 | Correct | 104 ms | 12192 KB | Ok |
44 | Correct | 165 ms | 21604 KB | Ok |
45 | Correct | 4 ms | 632 KB | Ok |
46 | Correct | 4 ms | 632 KB | Ok |
47 | Correct | 4 ms | 632 KB | Ok |
48 | Correct | 4 ms | 504 KB | Ok |
49 | Correct | 4 ms | 504 KB | Ok |
50 | Correct | 4 ms | 504 KB | Ok |
51 | Correct | 4 ms | 504 KB | Ok |
52 | Correct | 4 ms | 632 KB | Ok |
53 | Correct | 5 ms | 604 KB | Ok |
54 | Correct | 4 ms | 632 KB | Ok |
55 | Correct | 7 ms | 888 KB | Ok |
56 | Correct | 7 ms | 888 KB | Ok |
57 | Correct | 8 ms | 888 KB | Ok |
58 | Correct | 8 ms | 888 KB | Ok |
59 | Correct | 8 ms | 888 KB | Ok |
60 | Correct | 7 ms | 760 KB | Ok |
61 | Correct | 8 ms | 888 KB | Ok |
62 | Correct | 7 ms | 764 KB | Ok |
63 | Correct | 8 ms | 760 KB | Ok |
64 | Correct | 8 ms | 888 KB | Ok |
65 | Correct | 100 ms | 9000 KB | Ok |
66 | Correct | 115 ms | 8388 KB | Ok |
67 | Correct | 111 ms | 8592 KB | Ok |
68 | Correct | 84 ms | 7444 KB | Ok |
69 | Correct | 120 ms | 8880 KB | Ok |
70 | Correct | 105 ms | 7764 KB | Ok |
71 | Correct | 91 ms | 7404 KB | Ok |
72 | Correct | 91 ms | 8588 KB | Ok |
73 | Correct | 123 ms | 8496 KB | Ok |
74 | Correct | 95 ms | 7364 KB | Ok |
75 | Correct | 137 ms | 8324 KB | Ok |
76 | Correct | 111 ms | 8504 KB | Ok |
77 | Correct | 95 ms | 7960 KB | Ok |
78 | Correct | 86 ms | 8112 KB | Ok |
79 | Correct | 104 ms | 8164 KB | Ok |
80 | Correct | 278 ms | 14516 KB | Ok |
81 | Correct | 402 ms | 15676 KB | Ok |
82 | Correct | 331 ms | 12852 KB | Ok |
83 | Correct | 326 ms | 15028 KB | Ok |
84 | Correct | 339 ms | 13492 KB | Ok |
85 | Correct | 298 ms | 12856 KB | Ok |
86 | Correct | 329 ms | 13172 KB | Ok |
87 | Correct | 374 ms | 15544 KB | Ok |
88 | Correct | 318 ms | 12424 KB | Ok |
89 | Correct | 338 ms | 15312 KB | Ok |
90 | Correct | 375 ms | 14400 KB | Ok |
91 | Correct | 292 ms | 13628 KB | Ok |
92 | Correct | 307 ms | 14800 KB | Ok |
93 | Correct | 307 ms | 14256 KB | Ok |
94 | Correct | 315 ms | 13492 KB | Ok |
95 | Correct | 286 ms | 20708 KB | Ok |
96 | Correct | 462 ms | 30264 KB | Ok |
97 | Correct | 410 ms | 24640 KB | Ok |
98 | Correct | 300 ms | 25656 KB | Ok |
99 | Correct | 310 ms | 24472 KB | Ok |
100 | Correct | 411 ms | 23568 KB | Ok |
101 | Correct | 351 ms | 28548 KB | Ok |
102 | Correct | 399 ms | 26468 KB | Ok |
103 | Correct | 431 ms | 30544 KB | Ok |
104 | Correct | 461 ms | 34088 KB | Ok |
105 | Correct | 502 ms | 35624 KB | Ok |
106 | Correct | 382 ms | 30172 KB | Ok |
107 | Correct | 411 ms | 29068 KB | Ok |
108 | Correct | 500 ms | 35536 KB | Ok |
109 | Correct | 418 ms | 31468 KB | Ok |
110 | Execution timed out | 2051 ms | 50196 KB | Time limit exceeded |
111 | Halted | 0 ms | 0 KB | - |