编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#25796 #1. 快速排序 Accepted 100 63 ms 768 K C++ 11 / 926 B 123 2025-03-12 9:46:14
显示原始代码
#include <iostream>
#include <array>
#include <cstdlib>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

std::array<int, 2> partition(int* arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(&arr[++less], &arr[l++]);
        } else if (arr[l] > arr[r]) {
            swap(&arr[--more], &arr[l]);
        } else {
            l++;
        }
    }
    swap(&arr[more], &arr[r]);
    return std::array<int, 2>{ less + 1, more };
}

void quickSort(int* arr, int l, int r) {
    if (l < r) {
        swap(&arr[l + rand() % (r - l + 1)], &arr[r]);
        std::array<int, 2> p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}

int main() {
    int n;
    std::cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:63 ms
内存:768 KiB

输入文件(2.in

100000
548813502 592844616 715189364 844265744 602763370 857945619 544883177 847251737 423654796 62
<988624 bytes omitted>

答案文件(2.out

4010 20029 24208 32576 46285 55350 60569 72453 73696 99348 140054 145665 150375 163096 166440 186713
<988615 bytes omitted>

用户输出

4010 20029 24208 32576 46285 55350 60569 72453 73696 99348 140054 145665 150375 163096 166440 186713 187112 200094 201277 206954
<988587 bytes omitted>

系统信息

Exited with return code 0