QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292865 | #5529. Most Annoying Constructive Problem | ucup-team1447# | RE | 1ms | 3440kb | C++14 | 3.7kb | 2023-12-28 15:35:16 | 2023-12-28 15:35:16 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
std::vector<int> trans(std::vector<int> p)
{
std::vector<int> rk(p.size());
std::iota(rk.begin(), rk.end(), 0);
std::sort(rk.begin(), rk.end(), [&](const int &A, const int &B)
{ return p[A] < p[B]; });
for (std::size_t i = 0; i != p.size(); ++i)
p[rk[i]] = i;
return p;
}
int calc(std::vector<int> p)
{
bool v[p.size()][p.size()];
std::memset(v, false, sizeof(v));
for (std::size_t i = 0; i != p.size(); ++i)
for (std::size_t j = i; ++j != p.size();)
v[i][j] = p[i] > p[j];
for (std::size_t i = 0; i != p.size(); ++i)
for (std::size_t j = i; ++j != p.size();)
v[i][j] ^= v[i][j - 1];
for (std::size_t i = p.size() - 1; i--;)
for (std::size_t j = i; j != p.size(); ++j)
v[i][j] ^= v[i + 1][j];
int res = 0;
for (std::size_t i = 0; i != p.size(); ++i)
for (std::size_t j = i; j != p.size(); ++j)
res += v[i][j];
return res;
}
std::vector<int> insert(const std::vector<int> &p, std::vector<int>::const_iterator i, int v)
{
std::vector<int> res = p;
for (auto &i : res)
i += i >= v;
res.insert(res.begin() + (i - p.begin()), v);
return res;
}
int calcmax(int n) { return ((n - 1) * (n - 1) + 1 + (n == 3)) / 2; }
bool able(int n, int k) { return n >= 1 && 0 <= k && k <= calcmax(n); }
std::vector<int> gen(int n, int k)
{
if (n == 3 && k == 3)
return {2, 1, 0};
if (k == calcmax(n) - (n == 3))
{
std::vector<int> p;
for (int i = 0; i != n; ++i)
p.push_back(i & 1 ? i : i + 4);
return trans(p);
}
if (n % 2 == 0 && k == calcmax(n) - 1)
{
std::vector<int> p;
for (int i = 0; i != n; ++i)
p.push_back(i & 1 ? i + 4 : i);
return trans(p);
}
if (able(n - 2, k - n + 1))
{
std::vector<int> p = gen(n - 2, k - n + 1);
p.push_back(n - 1);
p.push_back(n - 2);
return p;
}
if (k < n)
{
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
if (k == n - 1)
std::swap(p[0], p[1]);
else if (k)
std::rotate(p.end() - k - 2, p.end() - k - 1, p.end() - k + 1);
return p;
}
std::vector<int> p = gen(n - 1, calcmax(n - 1));
for (int i = 0; i <= n; ++i)
{
int cur = calcmax(n - 1);
bool v = false;
for (int j = n - 1; j--;)
{
v ^= p[j] >= i;
cur += v ^ (j < n - 3 || (j == n - 3 && p[n - 3] > p[n - 2]));
}
if (cur == k)
return insert(p, p.end(), i);
}
std::cout << n << ' ' << k << std::endl;
assert(false);
}
int T, n, k;
signed main()
{
// freopen("data.in", "r", stdin) && freopen("data.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::cin >> n >> k;
if (able(n, k))
{
std::cout << "YES" << std::endl;
for (auto i : gen(n, k))
std::cout << i + 1 << ' ';
std::cout << std::endl;
assert(calc(gen(n, k)) == k);
}
else
std::cout << "NO" << std::endl;
// std::vector<int> p;
// std::iota(p.begin(), p.end(), 0);
// do
// {
// std::cout << calc(p);
// for (auto i : p)
// std::cout << ' ' << i;
// std::cout << std::endl;
// } while (std::next_permutation(p.begin(), p.end()));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3440kb
input:
4 1 0 3 3 4 1 6 15
output:
YES 1 YES 3 2 1 YES 1 3 4 2 NO
result:
ok Correct (4 test cases)
Test #2:
score: -100
Runtime Error
input:
5951 27 255 28 371 31 320 33 201 32 199 31 108 15 78 27 32 24 268 20 4 14 82 29 202 33 85 26 104 31 380 27 330 20 140 29 192 21 63 17 89 20 41 32 444 20 76 27 114 33 330 26 249 33 301 24 87 25 72 14 49 25 281 21 58 15 48 16 19 14 0 22 175 11 7 30 43 31 259 22 112 12 30 30 111 33 268 30 287 19 150 15...
output:
YES 21 183