oj.uz

Submission #993145

# Submission time Handle Problem Language Result Execution time Memory
993145 2024-06-05T11:01:58 Z tch1cherin Nice sequence (IZhO18_sequence) C++17
6 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

vector<bool> used;
vector<int> tout;
int T = 0;

void dfs(int u, int N, int M) {
  used[u] = true;
  if (u - M >= 0 && !used[u]) {
    dfs(u - M, N, M);
  }
  if (u + N < (int)used.size() && !used[u + N]) {
    dfs(u + N, N, M);
  }
  tout[u] = T++;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;
    int l = -1, r = 2 * (N + M) + 1;
    vector<int> answer;
    while (r > l + 1) {
      int mid = (l + r) / 2;
      used.assign(mid + 1, false);
      tout.resize(mid + 1);
      used.assign(mid + 1, false);
      for (int i = 0; i <= mid; i++) {
        if (!used[i]) {
          dfs(i, N, M);
        }
      }
      bool good = true;
      for (int i = 0; i <= mid; i++) {
        if (i + N <= mid && tout[i + N] > tout[i]) {
          good = false;
        }
        if (i - M >= 0 && tout[i - M] > tout[i]) {
          good = false;
        }
      }
      if (good) {
        l = mid;
        answer.resize(mid);
        for (int i = 0; i < mid; i++) {
          answer[i] = tout[i + 1] - tout[i];
        }
      } else {
        r = mid;
      }
    }
    cout << l << "\n";
    for (int i = 0; i < l; i++) {
      cout << answer[i] << " \n"[i + 1 == l];
    }
  }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Jury has the better answer : jans = 3, pans = 2
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Incorrect 0 ms 348 KB Jury has the better answer : jans = 3, pans = 2
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Jury has the better answer : jans = 5, pans = 3
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 0 ms 348 KB Ok
15 Incorrect 0 ms 348 KB Jury has the better answer : jans = 3, pans = 2
16 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Incorrect 1 ms 344 KB Jury has the better answer : jans = 3, pans = 2
14 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Incorrect 1 ms 344 KB Jury has the better answer : jans = 3, pans = 2
14 Halted 0 ms 0 KB -