oj.uz

Submission #343769

# Submission time Handle Problem Language Result Execution time Memory
343769 2021-01-04T13:14:04 Z Pety Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 48296 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) {
  memset(viz, 0, sizeof(viz));
  memset(val, 0, sizeof(val));
  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 = 1000000, 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 249 ms 30828 KB Ok
2 Correct 221 ms 30700 KB Ok
3 Correct 182 ms 9068 KB Ok
4 Correct 188 ms 8844 KB Ok
5 Correct 213 ms 8812 KB Ok
6 Correct 191 ms 13164 KB Ok
7 Correct 190 ms 8424 KB Ok
8 Correct 189 ms 13164 KB Ok
9 Correct 191 ms 8044 KB Ok
10 Correct 203 ms 18988 KB Ok
11 Correct 197 ms 8300 KB Ok
12 Correct 195 ms 8104 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 18924 KB Ok
2 Correct 200 ms 18924 KB Ok
3 Correct 223 ms 18924 KB Ok
4 Correct 226 ms 18924 KB Ok
5 Correct 216 ms 18924 KB Ok
6 Correct 222 ms 19308 KB Ok
7 Correct 242 ms 19564 KB Ok
8 Correct 268 ms 19228 KB Ok
9 Correct 232 ms 19692 KB Ok
10 Correct 246 ms 19436 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30700 KB Ok
2 Correct 282 ms 30828 KB Ok
3 Correct 232 ms 19052 KB Ok
4 Correct 212 ms 15084 KB Ok
5 Correct 219 ms 30828 KB Ok
6 Correct 226 ms 30700 KB Ok
7 Correct 265 ms 30828 KB Ok
8 Correct 202 ms 30700 KB Ok
9 Correct 203 ms 30700 KB Ok
10 Correct 214 ms 18916 KB Ok
11 Correct 192 ms 14956 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 19052 KB Ok
2 Correct 182 ms 10604 KB Ok
3 Correct 195 ms 8940 KB Ok
4 Correct 185 ms 8556 KB Ok
5 Correct 175 ms 8300 KB Ok
6 Correct 557 ms 18528 KB Ok
7 Correct 534 ms 19436 KB Ok
8 Correct 862 ms 22368 KB Ok
9 Correct 629 ms 20740 KB Ok
10 Correct 459 ms 13548 KB Ok
11 Correct 604 ms 20876 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 30828 KB Ok
2 Correct 221 ms 30700 KB Ok
3 Correct 182 ms 9068 KB Ok
4 Correct 188 ms 8844 KB Ok
5 Correct 213 ms 8812 KB Ok
6 Correct 191 ms 13164 KB Ok
7 Correct 190 ms 8424 KB Ok
8 Correct 189 ms 13164 KB Ok
9 Correct 191 ms 8044 KB Ok
10 Correct 203 ms 18988 KB Ok
11 Correct 197 ms 8300 KB Ok
12 Correct 195 ms 8104 KB Ok
13 Correct 89 ms 30700 KB Ok
14 Correct 282 ms 30828 KB Ok
15 Correct 232 ms 19052 KB Ok
16 Correct 212 ms 15084 KB Ok
17 Correct 219 ms 30828 KB Ok
18 Correct 226 ms 30700 KB Ok
19 Correct 265 ms 30828 KB Ok
20 Correct 202 ms 30700 KB Ok
21 Correct 203 ms 30700 KB Ok
22 Correct 214 ms 18916 KB Ok
23 Correct 192 ms 14956 KB Ok
24 Correct 190 ms 7276 KB Ok
25 Correct 188 ms 7404 KB Ok
26 Correct 191 ms 7404 KB Ok
27 Correct 184 ms 7276 KB Ok
28 Correct 182 ms 7680 KB Ok
29 Correct 194 ms 7276 KB Ok
30 Correct 178 ms 7440 KB Ok
31 Correct 185 ms 7404 KB Ok
32 Correct 185 ms 7532 KB Ok
33 Correct 196 ms 7532 KB Ok
34 Correct 200 ms 7752 KB Ok
35 Correct 199 ms 7532 KB Ok
36 Correct 202 ms 7644 KB Ok
37 Correct 206 ms 7532 KB Ok
38 Correct 217 ms 7660 KB Ok
39 Correct 201 ms 7532 KB Ok
40 Correct 232 ms 7532 KB Ok
41 Correct 199 ms 7532 KB Ok
42 Correct 201 ms 7748 KB Ok
43 Correct 205 ms 7660 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 30828 KB Ok
2 Correct 221 ms 30700 KB Ok
3 Correct 182 ms 9068 KB Ok
4 Correct 188 ms 8844 KB Ok
5 Correct 213 ms 8812 KB Ok
6 Correct 191 ms 13164 KB Ok
7 Correct 190 ms 8424 KB Ok
8 Correct 189 ms 13164 KB Ok
9 Correct 191 ms 8044 KB Ok
10 Correct 203 ms 18988 KB Ok
11 Correct 197 ms 8300 KB Ok
12 Correct 195 ms 8104 KB Ok
13 Correct 221 ms 18924 KB Ok
14 Correct 200 ms 18924 KB Ok
15 Correct 223 ms 18924 KB Ok
16 Correct 226 ms 18924 KB Ok
17 Correct 216 ms 18924 KB Ok
18 Correct 222 ms 19308 KB Ok
19 Correct 242 ms 19564 KB Ok
20 Correct 268 ms 19228 KB Ok
21 Correct 232 ms 19692 KB Ok
22 Correct 246 ms 19436 KB Ok
23 Correct 89 ms 30700 KB Ok
24 Correct 282 ms 30828 KB Ok
25 Correct 232 ms 19052 KB Ok
26 Correct 212 ms 15084 KB Ok
27 Correct 219 ms 30828 KB Ok
28 Correct 226 ms 30700 KB Ok
29 Correct 265 ms 30828 KB Ok
30 Correct 202 ms 30700 KB Ok
31 Correct 203 ms 30700 KB Ok
32 Correct 214 ms 18916 KB Ok
33 Correct 192 ms 14956 KB Ok
34 Correct 190 ms 7276 KB Ok
35 Correct 188 ms 7404 KB Ok
36 Correct 191 ms 7404 KB Ok
37 Correct 184 ms 7276 KB Ok
38 Correct 182 ms 7680 KB Ok
39 Correct 194 ms 7276 KB Ok
40 Correct 178 ms 7440 KB Ok
41 Correct 185 ms 7404 KB Ok
42 Correct 185 ms 7532 KB Ok
43 Correct 196 ms 7532 KB Ok
44 Correct 200 ms 7752 KB Ok
45 Correct 199 ms 7532 KB Ok
46 Correct 202 ms 7644 KB Ok
47 Correct 206 ms 7532 KB Ok
48 Correct 217 ms 7660 KB Ok
49 Correct 201 ms 7532 KB Ok
50 Correct 232 ms 7532 KB Ok
51 Correct 199 ms 7532 KB Ok
52 Correct 201 ms 7748 KB Ok
53 Correct 205 ms 7660 KB Ok
54 Correct 385 ms 9324 KB Ok
55 Correct 434 ms 9680 KB Ok
56 Correct 431 ms 9772 KB Ok
57 Correct 351 ms 8912 KB Ok
58 Correct 402 ms 9136 KB Ok
59 Correct 364 ms 8940 KB Ok
60 Correct 341 ms 8812 KB Ok
61 Correct 348 ms 8940 KB Ok
62 Correct 439 ms 9324 KB Ok
63 Correct 367 ms 9100 KB Ok
64 Correct 438 ms 9708 KB Ok
65 Correct 391 ms 9264 KB Ok
66 Correct 384 ms 9072 KB Ok
67 Correct 346 ms 9068 KB Ok
68 Correct 367 ms 9068 KB Ok
69 Correct 693 ms 18300 KB Ok
70 Correct 710 ms 18964 KB Ok
71 Correct 669 ms 18420 KB Ok
72 Correct 709 ms 18284 KB Ok
73 Correct 670 ms 18412 KB Ok
74 Correct 657 ms 18156 KB Ok
75 Correct 690 ms 17900 KB Ok
76 Correct 734 ms 18668 KB Ok
77 Correct 651 ms 17772 KB Ok
78 Correct 685 ms 18284 KB Ok
79 Correct 690 ms 18552 KB Ok
80 Correct 667 ms 18496 KB Ok
81 Correct 695 ms 18540 KB Ok
82 Correct 670 ms 18412 KB Ok
83 Correct 648 ms 18028 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 30828 KB Ok
2 Correct 221 ms 30700 KB Ok
3 Correct 182 ms 9068 KB Ok
4 Correct 188 ms 8844 KB Ok
5 Correct 213 ms 8812 KB Ok
6 Correct 191 ms 13164 KB Ok
7 Correct 190 ms 8424 KB Ok
8 Correct 189 ms 13164 KB Ok
9 Correct 191 ms 8044 KB Ok
10 Correct 203 ms 18988 KB Ok
11 Correct 197 ms 8300 KB Ok
12 Correct 195 ms 8104 KB Ok
13 Correct 221 ms 18924 KB Ok
14 Correct 200 ms 18924 KB Ok
15 Correct 223 ms 18924 KB Ok
16 Correct 226 ms 18924 KB Ok
17 Correct 216 ms 18924 KB Ok
18 Correct 222 ms 19308 KB Ok
19 Correct 242 ms 19564 KB Ok
20 Correct 268 ms 19228 KB Ok
21 Correct 232 ms 19692 KB Ok
22 Correct 246 ms 19436 KB Ok
23 Correct 89 ms 30700 KB Ok
24 Correct 282 ms 30828 KB Ok
25 Correct 232 ms 19052 KB Ok
26 Correct 212 ms 15084 KB Ok
27 Correct 219 ms 30828 KB Ok
28 Correct 226 ms 30700 KB Ok
29 Correct 265 ms 30828 KB Ok
30 Correct 202 ms 30700 KB Ok
31 Correct 203 ms 30700 KB Ok
32 Correct 214 ms 18916 KB Ok
33 Correct 192 ms 14956 KB Ok
34 Correct 224 ms 19052 KB Ok
35 Correct 182 ms 10604 KB Ok
36 Correct 195 ms 8940 KB Ok
37 Correct 185 ms 8556 KB Ok
38 Correct 175 ms 8300 KB Ok
39 Correct 557 ms 18528 KB Ok
40 Correct 534 ms 19436 KB Ok
41 Correct 862 ms 22368 KB Ok
42 Correct 629 ms 20740 KB Ok
43 Correct 459 ms 13548 KB Ok
44 Correct 604 ms 20876 KB Ok
45 Correct 190 ms 7276 KB Ok
46 Correct 188 ms 7404 KB Ok
47 Correct 191 ms 7404 KB Ok
48 Correct 184 ms 7276 KB Ok
49 Correct 182 ms 7680 KB Ok
50 Correct 194 ms 7276 KB Ok
51 Correct 178 ms 7440 KB Ok
52 Correct 185 ms 7404 KB Ok
53 Correct 185 ms 7532 KB Ok
54 Correct 196 ms 7532 KB Ok
55 Correct 200 ms 7752 KB Ok
56 Correct 199 ms 7532 KB Ok
57 Correct 202 ms 7644 KB Ok
58 Correct 206 ms 7532 KB Ok
59 Correct 217 ms 7660 KB Ok
60 Correct 201 ms 7532 KB Ok
61 Correct 232 ms 7532 KB Ok
62 Correct 199 ms 7532 KB Ok
63 Correct 201 ms 7748 KB Ok
64 Correct 205 ms 7660 KB Ok
65 Correct 385 ms 9324 KB Ok
66 Correct 434 ms 9680 KB Ok
67 Correct 431 ms 9772 KB Ok
68 Correct 351 ms 8912 KB Ok
69 Correct 402 ms 9136 KB Ok
70 Correct 364 ms 8940 KB Ok
71 Correct 341 ms 8812 KB Ok
72 Correct 348 ms 8940 KB Ok
73 Correct 439 ms 9324 KB Ok
74 Correct 367 ms 9100 KB Ok
75 Correct 438 ms 9708 KB Ok
76 Correct 391 ms 9264 KB Ok
77 Correct 384 ms 9072 KB Ok
78 Correct 346 ms 9068 KB Ok
79 Correct 367 ms 9068 KB Ok
80 Correct 693 ms 18300 KB Ok
81 Correct 710 ms 18964 KB Ok
82 Correct 669 ms 18420 KB Ok
83 Correct 709 ms 18284 KB Ok
84 Correct 670 ms 18412 KB Ok
85 Correct 657 ms 18156 KB Ok
86 Correct 690 ms 17900 KB Ok
87 Correct 734 ms 18668 KB Ok
88 Correct 651 ms 17772 KB Ok
89 Correct 685 ms 18284 KB Ok
90 Correct 690 ms 18552 KB Ok
91 Correct 667 ms 18496 KB Ok
92 Correct 695 ms 18540 KB Ok
93 Correct 670 ms 18412 KB Ok
94 Correct 648 ms 18028 KB Ok
95 Correct 659 ms 12528 KB Ok
96 Correct 928 ms 14572 KB Ok
97 Correct 875 ms 13676 KB Ok
98 Correct 663 ms 12396 KB Ok
99 Correct 798 ms 13164 KB Ok
100 Correct 823 ms 13060 KB Ok
101 Correct 855 ms 13628 KB Ok
102 Correct 831 ms 13464 KB Ok
103 Correct 804 ms 13548 KB Ok
104 Correct 943 ms 14624 KB Ok
105 Correct 897 ms 14316 KB Ok
106 Correct 788 ms 14036 KB Ok
107 Correct 862 ms 13932 KB Ok
108 Correct 956 ms 14700 KB Ok
109 Correct 871 ms 14444 KB Ok
110 Execution timed out 2029 ms 48296 KB Time limit exceeded
111 Halted 0 ms 0 KB -