QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#365016#8110. Additionckiseki#WA 13ms102100kbC++202.7kb2024-03-24 18:10:192024-03-24 18:10:19

Judging History

你现在查看的是最新测评结果

  • [2024-03-24 18:10:19]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:102100kb
  • [2024-03-24 18:10:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe

#define orange(...) safe
#endif

constexpr int N = 250'000 + 5;
constexpr int L = 50;

constexpr int64_t INF = 1LL << 60;

int64_t dp1[L][L * (L - 1) / 2 + 1];
int64_t dp2[N][L];

int64_t add(int64_t a, int64_t b) {
  return min(a + b, INF);
}

int64_t sub(int64_t a, int64_t b) {
  if (a == INF)
    return INF;
  return a - b;
}


int ans[N];

int64_t calc(int len, int64_t inv) {
  const int64_t max_inv = int64_t(len) * (len - 1) / 2;
  if (0 > inv or inv > max_inv)
    return 0;
  if (len < L) {
    return dp1[len][inv];
  }
  if (inv >= L)
    return INF;
  return dp2[len][inv];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  dp1[0][0] = 1;
  dp1[1][0] = 1;
  for (int i = 2; i < L; ++i) {
    const int inv = (i - 2) * (i - 1) / 2;
    for (int j = 0; j <= inv; ++j) {
      for (int k = 0; k <= i - 1; ++k) {
        dp1[i][j + k] = add(dp1[i][j + k], dp1[i - 1][j]);
      }
    }
  }
  dp2[0][0] = 1;
  dp2[1][0] = 1;
  for (int i = 2; i < N; ++i) {
    const int64_t inv = min<int64_t>(L - 1, int64_t(i - 1) * i / 2);
    int64_t sm = 0;
    for (int j = 0; j <= inv; ++j) {
      sm = add(sm, dp2[i - 1][j]);
      if ((j - (i - 1) - 1) >= 0)
        sm = sub(sm, dp2[i - 1][j - (i - 1) - 1]);
      dp2[i][j] = sm;
      // dp2[i][j] = dp2[i - 1][j - (i - 1)] + ... + dp2[i - 1][j]
    }
  }

  int n;
  int64_t k;
  cin >> n >> k;

  if (n % 4 == 3) {
    cout << "NO\n";
    return 0;
  }

  int64_t inv = int64_t(n) * (n - 1) / 4;

  list<int> exists;
  for (int i = 1; i <= n; ++i)
    exists.push_back(i);

  for (int i = 0; i < n; ++i) {
    bool found = false;
    for (auto it = exists.begin(); it != exists.end(); ++it) {
      ans[i] = *it;
      int64_t cur = calc(n - i - 1, inv);
      if (k - cur > 0) {
        inv -= 1;
        k -= cur;
      } else {
        found = true;
        exists.erase(it);
        break;
      }
    }
    if (not found) {
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n";
  for (int i = 0; i < n; ++i)
    cout << ans[i] << " \n"[i + 1 == n];
  return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 102100kb

input:

1

output:

NO

result:

wrong output format Expected integer, but "NO" found