QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#365016 | #8110. Addition | ckiseki# | WA | 13ms | 102100kb | C++20 | 2.7kb | 2024-03-24 18:10:19 | 2024-03-24 18:10:19 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 102100kb
input:
1
output:
NO
result:
wrong output format Expected integer, but "NO" found