Submission #785691

#	Time	Username	Problem	Language	Result	Execution time	Memory
785691		Soumya1	Nice sequence (IZhO18_sequence)	C++17	100 / 100	972 ms	32748 KiB

sequence

#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
void testCase() {
  int n, m;
  cin >> n >> m;
  int lo = 0, hi = 2 * (n + m);
  vector<int> q;
  auto check = [&](int l) {
    vector<int> deg(l + 1);
    for (int i = 0; i <= l; i++) {
      if (i - n >= 0) deg[i - n]++;
      if (i + m <= l) deg[i + m]++;
    }
    q.clear();
    for (int i = 0; i <= l; i++) {
      if (!deg[i]) q.push_back(i);
    }
    for (int i = 0; i < q.size(); i++) {
      int u = q[i];
      for (int v : {u - n, u + m}) {
        if (v >= 0 && v <= l) {
          deg[v]--;
          if (!deg[v]) q.push_back(v);
        }
      }
    }
    return (q.size() == l + 1);
  };
  while (lo < hi) {
    int mid = (lo + hi + 1) >> 1;
    if (check(mid)) lo = mid;
    else hi = mid - 1;
  }
  check(lo);
  vector<int> ans(lo + 1);
  for (int i = 0; i <= lo; i++) {
    ans[q[i]] = i;
  }
  cout << lo << "\n";
  for (int i = 1; i <= lo; i++) {
    cout << ans[i] - ans[i - 1] << " ";
  }
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tc;
  cin >> tc;
  while (tc--) {
    testCase();
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
sequence.cpp:30:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     return (q.size() == l + 1);
      |             ~~~~~~~~~^~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24