oj.uz

답안 #343748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343748 2021-01-04T12:55:48 Z Pety Nice sequence (IZhO18_sequence) C++14
0 / 100
 196 ms 110108 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));
  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 <= n; 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;
    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;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:45:31: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     int st = 1, dr = 1000000, sol;
      |                               ^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 110108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 196 ms 17036 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 28780 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 17132 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 110108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 110108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 110108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -