oj.uz

Submission #343772

# Submission time Handle Problem Language Result Execution time Memory
343772 2021-01-04T13:16:34 Z Pety Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 47320 KB 
#include <bits/stdc++.h>


using namespace std;

int top[1000002], k, ans[1000002], val[1000002], n, m;
bool viz[1000002];

void dfs (int x, int len) {
  viz[x] = 1;
  if (x + n <= len && !viz[x + n])
    dfs(x + n, len);
  if (x - m >= 0 && !viz[x - m])
    dfs(x - m, len);
  top[++k] = x;
}

bool ok (int len) {
  for (int i = 0;i <= len; i++)
    val[i] = viz[i] = 0;
  k = 0;
  for (int i = 0; i <= len; i++)
    if (!viz[i])
      dfs(i, len);
  for (int i = 1; i <= len + 1; i++)
    val[top[i]] = i;
  for (int i = 0; i <= len; i++) {
    if (i >= n && val[i] > val[i - n])
      return false;
    if (i + m <= len && val[i] > val[i + m])
      return false;
  }
  for (int i = 1; i <= len; i++)
    ans[i] = val[i] - val[i - 1];
  return true;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    cin >> n >> m;
    int st = 1, dr = 500000, sol = 0;
    while (st <= dr) {
      int mij = (st + dr) / 2;
      if (ok(mij)) {
        sol = mij;
        st = mij + 1;
      }
      else
        dr = mij - 1;
    }
    cout << sol << "\n";
    ok(sol);
    for (int i = 1; i <= sol; i++)
      cout << ans[i] << " ";
    cout << "\n";
  }
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14316 KB Ok
2 Correct 86 ms 14316 KB Ok
3 Correct 68 ms 3520 KB Ok
4 Correct 68 ms 3436 KB Ok
5 Correct 67 ms 3564 KB Ok
6 Correct 70 ms 5484 KB Ok
7 Correct 72 ms 3180 KB Ok
8 Correct 71 ms 5484 KB Ok
9 Correct 68 ms 2924 KB Ok
10 Correct 72 ms 8428 KB Ok
11 Correct 68 ms 3180 KB Ok
12 Correct 67 ms 2924 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 8428 KB Ok
2 Correct 78 ms 8480 KB Ok
3 Correct 77 ms 8480 KB Ok
4 Correct 79 ms 8480 KB Ok
5 Correct 79 ms 8480 KB Ok
6 Correct 85 ms 8556 KB Ok
7 Correct 100 ms 9068 KB Ok
8 Correct 91 ms 8684 KB Ok
9 Correct 107 ms 9196 KB Ok
10 Correct 93 ms 8824 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 14316 KB Ok
2 Correct 100 ms 14316 KB Ok
3 Correct 83 ms 8428 KB Ok
4 Correct 69 ms 6508 KB Ok
5 Correct 79 ms 14316 KB Ok
6 Correct 77 ms 14316 KB Ok
7 Correct 81 ms 14316 KB Ok
8 Correct 75 ms 14316 KB Ok
9 Correct 75 ms 14316 KB Ok
10 Correct 76 ms 8440 KB Ok
11 Correct 68 ms 6508 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8428 KB Ok
2 Correct 66 ms 4204 KB Ok
3 Correct 66 ms 3436 KB Ok
4 Correct 65 ms 3300 KB Ok
5 Correct 67 ms 3052 KB Ok
6 Correct 393 ms 13676 KB Ok
7 Correct 382 ms 14828 KB Ok
8 Correct 712 ms 17388 KB Ok
9 Correct 489 ms 15724 KB Ok
10 Correct 298 ms 9068 KB Ok
11 Correct 487 ms 16108 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14316 KB Ok
2 Correct 86 ms 14316 KB Ok
3 Correct 68 ms 3520 KB Ok
4 Correct 68 ms 3436 KB Ok
5 Correct 67 ms 3564 KB Ok
6 Correct 70 ms 5484 KB Ok
7 Correct 72 ms 3180 KB Ok
8 Correct 71 ms 5484 KB Ok
9 Correct 68 ms 2924 KB Ok
10 Correct 72 ms 8428 KB Ok
11 Correct 68 ms 3180 KB Ok
12 Correct 67 ms 2924 KB Ok
13 Correct 32 ms 14316 KB Ok
14 Correct 100 ms 14316 KB Ok
15 Correct 83 ms 8428 KB Ok
16 Correct 69 ms 6508 KB Ok
17 Correct 79 ms 14316 KB Ok
18 Correct 77 ms 14316 KB Ok
19 Correct 81 ms 14316 KB Ok
20 Correct 75 ms 14316 KB Ok
21 Correct 75 ms 14316 KB Ok
22 Correct 76 ms 8440 KB Ok
23 Correct 68 ms 6508 KB Ok
24 Correct 70 ms 2796 KB Ok
25 Correct 72 ms 2668 KB Ok
26 Correct 70 ms 2668 KB Ok
27 Correct 71 ms 2668 KB Ok
28 Correct 70 ms 2796 KB Ok
29 Correct 67 ms 2668 KB Ok
30 Correct 70 ms 2668 KB Ok
31 Correct 69 ms 2668 KB Ok
32 Correct 69 ms 2668 KB Ok
33 Correct 68 ms 2668 KB Ok
34 Correct 78 ms 2796 KB Ok
35 Correct 80 ms 2924 KB Ok
36 Correct 80 ms 2924 KB Ok
37 Correct 84 ms 2876 KB Ok
38 Correct 79 ms 2924 KB Ok
39 Correct 79 ms 3052 KB Ok
40 Correct 81 ms 2924 KB Ok
41 Correct 78 ms 2924 KB Ok
42 Correct 78 ms 2924 KB Ok
43 Correct 80 ms 3052 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14316 KB Ok
2 Correct 86 ms 14316 KB Ok
3 Correct 68 ms 3520 KB Ok
4 Correct 68 ms 3436 KB Ok
5 Correct 67 ms 3564 KB Ok
6 Correct 70 ms 5484 KB Ok
7 Correct 72 ms 3180 KB Ok
8 Correct 71 ms 5484 KB Ok
9 Correct 68 ms 2924 KB Ok
10 Correct 72 ms 8428 KB Ok
11 Correct 68 ms 3180 KB Ok
12 Correct 67 ms 2924 KB Ok
13 Correct 85 ms 8428 KB Ok
14 Correct 78 ms 8480 KB Ok
15 Correct 77 ms 8480 KB Ok
16 Correct 79 ms 8480 KB Ok
17 Correct 79 ms 8480 KB Ok
18 Correct 85 ms 8556 KB Ok
19 Correct 100 ms 9068 KB Ok
20 Correct 91 ms 8684 KB Ok
21 Correct 107 ms 9196 KB Ok
22 Correct 93 ms 8824 KB Ok
23 Correct 32 ms 14316 KB Ok
24 Correct 100 ms 14316 KB Ok
25 Correct 83 ms 8428 KB Ok
26 Correct 69 ms 6508 KB Ok
27 Correct 79 ms 14316 KB Ok
28 Correct 77 ms 14316 KB Ok
29 Correct 81 ms 14316 KB Ok
30 Correct 75 ms 14316 KB Ok
31 Correct 75 ms 14316 KB Ok
32 Correct 76 ms 8440 KB Ok
33 Correct 68 ms 6508 KB Ok
34 Correct 70 ms 2796 KB Ok
35 Correct 72 ms 2668 KB Ok
36 Correct 70 ms 2668 KB Ok
37 Correct 71 ms 2668 KB Ok
38 Correct 70 ms 2796 KB Ok
39 Correct 67 ms 2668 KB Ok
40 Correct 70 ms 2668 KB Ok
41 Correct 69 ms 2668 KB Ok
42 Correct 69 ms 2668 KB Ok
43 Correct 68 ms 2668 KB Ok
44 Correct 78 ms 2796 KB Ok
45 Correct 80 ms 2924 KB Ok
46 Correct 80 ms 2924 KB Ok
47 Correct 84 ms 2876 KB Ok
48 Correct 79 ms 2924 KB Ok
49 Correct 79 ms 3052 KB Ok
50 Correct 81 ms 2924 KB Ok
51 Correct 78 ms 2924 KB Ok
52 Correct 78 ms 2924 KB Ok
53 Correct 80 ms 3052 KB Ok
54 Correct 264 ms 4588 KB Ok
55 Correct 301 ms 4972 KB Ok
56 Correct 293 ms 5060 KB Ok
57 Correct 220 ms 4204 KB Ok
58 Correct 260 ms 4460 KB Ok
59 Correct 243 ms 4332 KB Ok
60 Correct 219 ms 4076 KB Ok
61 Correct 232 ms 4332 KB Ok
62 Correct 285 ms 4716 KB Ok
63 Correct 244 ms 4460 KB Ok
64 Correct 292 ms 4972 KB Ok
65 Correct 266 ms 4588 KB Ok
66 Correct 247 ms 4460 KB Ok
67 Correct 222 ms 4332 KB Ok
68 Correct 254 ms 4568 KB Ok
69 Correct 518 ms 13676 KB Ok
70 Correct 547 ms 14188 KB Ok
71 Correct 493 ms 13676 KB Ok
72 Correct 545 ms 13548 KB Ok
73 Correct 508 ms 13676 KB Ok
74 Correct 497 ms 13548 KB Ok
75 Correct 516 ms 13292 KB Ok
76 Correct 560 ms 13932 KB Ok
77 Correct 493 ms 13164 KB Ok
78 Correct 524 ms 13676 KB Ok
79 Correct 524 ms 13804 KB Ok
80 Correct 520 ms 13940 KB Ok
81 Correct 543 ms 13804 KB Ok
82 Correct 521 ms 13804 KB Ok
83 Correct 495 ms 13248 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14316 KB Ok
2 Correct 86 ms 14316 KB Ok
3 Correct 68 ms 3520 KB Ok
4 Correct 68 ms 3436 KB Ok
5 Correct 67 ms 3564 KB Ok
6 Correct 70 ms 5484 KB Ok
7 Correct 72 ms 3180 KB Ok
8 Correct 71 ms 5484 KB Ok
9 Correct 68 ms 2924 KB Ok
10 Correct 72 ms 8428 KB Ok
11 Correct 68 ms 3180 KB Ok
12 Correct 67 ms 2924 KB Ok
13 Correct 85 ms 8428 KB Ok
14 Correct 78 ms 8480 KB Ok
15 Correct 77 ms 8480 KB Ok
16 Correct 79 ms 8480 KB Ok
17 Correct 79 ms 8480 KB Ok
18 Correct 85 ms 8556 KB Ok
19 Correct 100 ms 9068 KB Ok
20 Correct 91 ms 8684 KB Ok
21 Correct 107 ms 9196 KB Ok
22 Correct 93 ms 8824 KB Ok
23 Correct 32 ms 14316 KB Ok
24 Correct 100 ms 14316 KB Ok
25 Correct 83 ms 8428 KB Ok
26 Correct 69 ms 6508 KB Ok
27 Correct 79 ms 14316 KB Ok
28 Correct 77 ms 14316 KB Ok
29 Correct 81 ms 14316 KB Ok
30 Correct 75 ms 14316 KB Ok
31 Correct 75 ms 14316 KB Ok
32 Correct 76 ms 8440 KB Ok
33 Correct 68 ms 6508 KB Ok
34 Correct 77 ms 8428 KB Ok
35 Correct 66 ms 4204 KB Ok
36 Correct 66 ms 3436 KB Ok
37 Correct 65 ms 3300 KB Ok
38 Correct 67 ms 3052 KB Ok
39 Correct 393 ms 13676 KB Ok
40 Correct 382 ms 14828 KB Ok
41 Correct 712 ms 17388 KB Ok
42 Correct 489 ms 15724 KB Ok
43 Correct 298 ms 9068 KB Ok
44 Correct 487 ms 16108 KB Ok
45 Correct 70 ms 2796 KB Ok
46 Correct 72 ms 2668 KB Ok
47 Correct 70 ms 2668 KB Ok
48 Correct 71 ms 2668 KB Ok
49 Correct 70 ms 2796 KB Ok
50 Correct 67 ms 2668 KB Ok
51 Correct 70 ms 2668 KB Ok
52 Correct 69 ms 2668 KB Ok
53 Correct 69 ms 2668 KB Ok
54 Correct 68 ms 2668 KB Ok
55 Correct 78 ms 2796 KB Ok
56 Correct 80 ms 2924 KB Ok
57 Correct 80 ms 2924 KB Ok
58 Correct 84 ms 2876 KB Ok
59 Correct 79 ms 2924 KB Ok
60 Correct 79 ms 3052 KB Ok
61 Correct 81 ms 2924 KB Ok
62 Correct 78 ms 2924 KB Ok
63 Correct 78 ms 2924 KB Ok
64 Correct 80 ms 3052 KB Ok
65 Correct 264 ms 4588 KB Ok
66 Correct 301 ms 4972 KB Ok
67 Correct 293 ms 5060 KB Ok
68 Correct 220 ms 4204 KB Ok
69 Correct 260 ms 4460 KB Ok
70 Correct 243 ms 4332 KB Ok
71 Correct 219 ms 4076 KB Ok
72 Correct 232 ms 4332 KB Ok
73 Correct 285 ms 4716 KB Ok
74 Correct 244 ms 4460 KB Ok
75 Correct 292 ms 4972 KB Ok
76 Correct 266 ms 4588 KB Ok
77 Correct 247 ms 4460 KB Ok
78 Correct 222 ms 4332 KB Ok
79 Correct 254 ms 4568 KB Ok
80 Correct 518 ms 13676 KB Ok
81 Correct 547 ms 14188 KB Ok
82 Correct 493 ms 13676 KB Ok
83 Correct 545 ms 13548 KB Ok
84 Correct 508 ms 13676 KB Ok
85 Correct 497 ms 13548 KB Ok
86 Correct 516 ms 13292 KB Ok
87 Correct 560 ms 13932 KB Ok
88 Correct 493 ms 13164 KB Ok
89 Correct 524 ms 13676 KB Ok
90 Correct 524 ms 13804 KB Ok
91 Correct 520 ms 13940 KB Ok
92 Correct 543 ms 13804 KB Ok
93 Correct 521 ms 13804 KB Ok
94 Correct 495 ms 13248 KB Ok
95 Correct 552 ms 7836 KB Ok
96 Correct 847 ms 10988 KB Ok
97 Correct 820 ms 10112 KB Ok
98 Correct 582 ms 9068 KB Ok
99 Correct 722 ms 9524 KB Ok
100 Correct 728 ms 9700 KB Ok
101 Correct 743 ms 9884 KB Ok
102 Correct 752 ms 9888 KB Ok
103 Correct 718 ms 9708 KB Ok
104 Correct 876 ms 11244 KB Ok
105 Correct 810 ms 10708 KB Ok
106 Correct 698 ms 10336 KB Ok
107 Correct 779 ms 10348 KB Ok
108 Correct 856 ms 10948 KB Ok
109 Correct 786 ms 11268 KB Ok
110 Execution timed out 2039 ms 47320 KB Time limit exceeded
111 Halted 0 ms 0 KB -