代码

// ch7344 "鸭子排队" -- SUBMISSION 1.
//
// TASK: read n (4 B, LE) then n non-negative ints (4 B each, LE) from stdin;
//       output an arrangement of those n numbers in which a[i/2] <= a[i] for every i>1.
//       The statement proves ascending order is always valid, so: SORT and emit.
//
// WHY HEAPSORT, AND WHY EXACTLY ONE BUFFER:
//   * space limit 800 KB.  The statement says an I/O-ONLY program already costs 796 KB
//     (400 KB static array + 400 KB of memory-redirected stdout, charged to us).
//     => FOUR KB OF HEADROOM.  A second 400 KB buffer is an automatic MLE, and so is any
//     recursion, any std::vector, any std::sort/stable_sort that allocates.
//   * heapsort is in place with O(1) auxiliary state (one register temp per sift) and no
//     recursion, so a[100001] is the ONLY 400 KB object in the program.
//   * n <= 1e5 => ~1.7e6 comparisons, trivially inside 100 ms.
//   * only <stdio.h>: the statement asks for no unnecessary headers, and text pages count.
//
// The read buffer IS the sort buffer IS the write buffer: fread straight into a[],
// sort a[1..n] in place, fwrite from a+1.  The sample program does the same addressing
// (a[0] = n, ducks at a[1..n]) -- we add nothing to its footprint.
#include <stdio.h>

unsigned a[100001];

int main() {
    // one read, straight into the buffer (glibc bypasses the FILE buffer for a request
    // this large, so there is no hidden second copy).
    fread(a, 1, sizeof(a), stdin);
    unsigned n = a[0];

    if (n > 1) {
        // ---- build max-heap over a[1..n] ----
        for (unsigned i = n >> 1; i > 0; --i) {
            unsigned v = a[i], j = i, m = n;
            while ((j << 1) <= m) {
                unsigned c = j << 1;
                if (c < m && a[c] < a[c + 1]) ++c;
                if (v >= a[c]) break;
                a[j] = a[c];
                j = c;
            }
            a[j] = v;
        }
        // ---- repeatedly move the max to the end ----
        for (unsigned e = n; e > 1; --e) {
            unsigned v = a[e];
            a[e] = a[1];
            unsigned j = 1, m = e - 1;
            while ((j << 1) <= m) {
                unsigned c = j << 1;
                if (c < m && a[c] < a[c + 1]) ++c;
                if (v >= a[c]) break;
                a[j] = a[c];
                j = c;
            }
            a[j] = v;
        }
    }

    fwrite(a + 1, 1, (size_t)n * 4, stdout);
    return 0;
}

评测结果