QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292865#5529. Most Annoying Constructive Problemucup-team1447#RE 1ms3440kbC++143.7kb2023-12-28 15:35:162023-12-28 15:35:16

Judging History

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

  • [2023-12-28 15:35:16]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3440kb
  • [2023-12-28 15:35:16]
  • 提交

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

result: