QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#219564 | #5143. Quick Sort | xuyufeiya | WA | 40ms | 5828kb | C++20 | 2.1kb | 2023-10-19 16:19:32 | 2023-10-19 16:19:32 |
Judging History
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'