记录编号	416862	评测结果	AAAAAAAAAAA
题目名称	637.排序测试	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	1.819 s
提交时间	2017-06-22 21:17:58	内存使用	31.82 MiB

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

const int MAXN = 2e6 + 10;

namespace IO{
    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 in(void){
        register int res = 0;
        register char tmp = getc();
        while(!isdigit(tmp)) tmp = getc();
        while(isdigit(tmp))
            res = (res + (res << 2) << 1) + (tmp ^ 48),
            tmp = getc();
        return res;
    }

    char op[1 << 24], *ops = op;
    char tmp[14];

    inline void write(int x){
        if(!x){
            *ops = '0';
            *(ops + 1) = ' ';
            ops += 2;
            return ;
        }

        register char *p = tmp;
        while(x){
            *(++p) = (x % 10) | 0x30;
            x /= 10;
        }

        while(*p) *(ops++) = *(p--);
        *(ops++) = ' ';
        return ;
    }

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

using IO::in;
using IO::write;
using IO::write_all;

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

int s[MAXN];
int N;

int main(){ 
#ifndef LOCAL
    freopen("sorttest.in", "r", stdin);
    freopen("sorttest.out", "w", stdout);
#endif
    N = in();

    for(int i = 1; i <= N; ++i) s[i] = in();
    gb(s + 1, s + N);

    for(int i = 1; i <= N; ++i) write(s[i]);
    write_all();
    return 0;
}

void gb(int *l, int *r){
    static int p[MAXN];
    if(l == r) return ;
    register int *mid = l + ((r - l) >> 1);
    gb(l, mid);
    gb(mid + 1, r);

    register int *k = p;
    register int *i = l, *j = mid + 1;

    while(i <= mid && j <= r){
        if(*i < *j) *(k++) = *(i++);
        else *(k++) = *(j++);
    }

    while(i <= mid) *(k++) = *(i++);
    while(j <= r) *(k++) = *(j++);

    k = p;
    for(; l <= r; ++l) *l = *(k++);

    return ;
}