QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#219564#5143. Quick SortxuyufeiyaWA 40ms5828kbC++202.1kb2023-10-19 16:19:322023-10-19 16:19:32

Judging History

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

  • [2023-10-19 16:19:32]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:5828kb
  • [2023-10-19 16:19:32]
  • 提交

answer

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

const int N = 5e5 + 10;
int a[N], pos[N];

void solve()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    int cnt = 0;

    auto dfs = [&](auto self, int l, int r) {
        if(l >= r)  return;
        int mid = (l + r + 1) / 2, midVal = a[mid];
        // printf("::%d %d %d %d\n", l, r, mid, midVal);
        vector<int> lp, rp;
        if(midVal < mid) {
            for(int i = l; i <= midVal; i++)    if(a[i] >= midVal && i != a[i])    lp.push_back(i);
            for(int v = l; v <= midVal; v++)    if(pos[v] >= midVal && pos[v] != v)     rp.push_back(pos[v]);
            sort(rp.begin(), rp.end(), greater<int>());
        } else if(midVal >= mid) {
            for(int v = midVal; v <= r; v++)    if(pos[v] <= midVal && pos[v] != v) lp.push_back(pos[v]);
            for(int i = midVal; i <= r; i++)    if(a[i] <= midVal && i != a[i])   rp.push_back(i);
            sort(lp.begin(), lp.end());
        }
        // assert(lp.size() == rp.size());
        // if(lp.size() != rp.size()) {
        //     printf("___\n");
        //     for(int i = 1; i <= n; i++) printf("%d ", a[i]);
        //     printf("\n");
        //     for(int p: lp)  printf("%d ", p);
        //     printf("\n");
        //     for(int p: rp)  printf("%d ", p);
        //     printf("\n");
        // }

        for(int i = 0; i < lp.size(); i++) {
            int p1 = lp[i], p2 = rp[i];
            if(p1 == p2)    continue;
            // printf("::::%d %d %d %d\n", p1, a[p1], p2, a[p2]);
            swap(a[p1], a[p2]);
            swap(pos[a[p1]], pos[a[p2]]);
            cnt++;
        }

            // printf("___\n");
            // for(int i = 1; i <= n; i++) printf("%d ", a[i]);
            // printf("\n");
        self(self, l, midVal - 1);
        self(self, midVal + 1, r);
    };    
    dfs(dfs, 1, n);
    printf("%d\n", cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)  solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5816kb

input:

3
3
3 2 1
5
2 4 5 3 1
10
7 2 4 6 1 9 10 8 5 3

output:

1
4
7

result:

ok 3 number(s): "1 4 7"

Test #2:

score: -100
Wrong Answer
time: 40ms
memory: 5828kb

input:

100000
4
3 4 2 1
5
5 4 1 3 2
4
3 1 4 2
4
4 2 1 3
4
1 3 2 4
4
4 2 3 1
4
3 2 1 4
5
1 2 3 4 5
5
5 2 3 1 4
5
1 3 5 4 2
5
4 3 2 1 5
5
3 4 2 1 5
5
5 4 3 2 1
4
3 4 2 1
5
4 2 5 1 3
5
4 1 5 2 3
4
3 4 1 2
4
2 1 3 4
5
4 3 2 5 1
4
4 2 1 3
5
3 1 5 2 4
4
4 1 2 3
5
1 5 2 4 3
5
4 1 3 5 2
5
4 2 3 5 1
5
1 2 3 4 5
5
4...

output:

3
4
3
2
1
1
1
0
2
2
2
3
4
3
2
3
2
1
3
2
4
2
2
3
2
0
4
2
3
1
3
2
3
2
1
1
4
1
1
2
4
3
1
3
1
1
1
2
2
3
4
4
2
3
3
2
3
2
3
2
1
1
1
4
1
3
1
1
3
3
2
2
4
1
1
3
2
2
2
2
1
3
3
3
3
3
2
2
1
3
2
3
2
4
3
2
1
4
2
3
4
1
2
2
3
2
2
3
2
2
2
2
4
1
2
3
2
2
2
2
3
2
3
4
3
1
3
4
2
3
1
3
2
3
4
3
3
2
1
2
4
3
3
3
2
4
3
1
2
2
...

result:

wrong answer 13th numbers differ - expected: '2', found: '4'