QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292864#5529. Most Annoying Constructive Problemucup-team1447#WA 1ms4132kbC++143.7kb2023-12-28 15:34:592023-12-28 15:34:59

Judging History

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

  • [2023-12-28 15:34:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4132kb
  • [2023-12-28 15:34:59]
  • 提交

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: 0
Wrong Answer
time: 1ms
memory: 4132kb

input:

4
1 0
3 3
4 1
6 15

output:


result:

wrong output format Unexpected end of file - token expected (test case 1)