Submission #343790

#TimeUsernameProblemLanguageResultExecution timeMemory
343790PetyNice sequence (IZhO18_sequence)C++14
100 / 100
1450 ms52988 KiB
#include <bits/stdc++.h>
#pragma GCC optimize ("O1")
#pragma GCC optimize ("O3")

using namespace std;

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

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 (i = 0;i <= len; i++)
    val[i] = viz[i] = 0;
  k = 0;
  for (i = 0; i <= len; i++)
    if (!viz[i])
      dfs(i, len);
  for (i = 1; i <= len + 1; i++)
    val[top[i]] = i;
  for (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 (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 T = 1; T <= t; T++) {
    cin >> n >> m;
    int sol = 0;
    for (int pas = (1 << 19); pas; (pas >>= 1))
      if (sol + pas <= n + m && ok(sol + pas))
        sol += pas;
    cout << sol << "\n";
    ok(sol);
    for (int j = 1; j <= sol; j++)
      cout << ans[j] << " ";
    cout << "\n";
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...