记录编号	434315	评测结果	AAAAAAAAAAA
题目名称	637.排序测试	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	1.825 s
提交时间	2017-08-07 18:16:35	内存使用	8.44 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    register bool f = true;
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = false, tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    if(f) return res;
    return ~res + 1;
}

char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);

inline void write_all(void) { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops; return ;
}

inline void write(int x) { 
    static char *p = new char[20]();
    do{ 
        *(++p) = (x % 10) | 0x30;
        x /= 10;
    }while(x);
    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) write_all();
    }
    *(opt++) = ' ';
    if(opt == opt_end) write_all();
    return ;
}

#define MAXN (2000010)

void qsort(int *l, int *r);

int s[MAXN];

int main() { 
#ifndef LOCAL
    freopen("sorttest.in", "r", stdin);
    freopen("sorttest.out", "w", stdout);
#endif
    int N = read();;
    srand(N);
    int *p = s;
    for(int i = 0; i < N; ++i) *(p++) = read();
    qsort(s, s + N);
    p = s;
    for(int i = 0; i < N; ++i) write(*(p++));
    write_all();
    return 0;
}

void qsort(int *l, int *r) { 
    int *i = l, *j = r - 1, temp;
    int mid = *(l + (rand() % (r - l)));
    do{ 
        while(*i < mid) ++i;
        while(mid < *j) --j;
        if(i <= j) { 
            temp = *i, *i = *j, *j = temp;
            ++i, --j;
        }
    }while(i <= j);
    if(l < j) qsort(l, j + 1);
    if(i < r - 1) qsort(i, r);
    return ;
}