Pagini recente » Borderou de evaluare (job #203617) | Cod sursa (job #1366690)
#include <stdio.h>
#include <ctype.h>
class InParser
{
private:
FILE *f;
char buf[4096];
int pos;
public:
InParser(const char* _name)
{
f = fopen(_name, "r");
pos = 4096;
}
InParser(FILE * _f)
{
f = _f;
pos = 4096;
}
~InParser()
{
fclose(f);
}
int getChar()
{
if (pos == 4096) {
fread(buf, 1, 4096, f);
pos = 0;
}
return buf[pos++];
}
int getInt()
{
int res = 0, c;
do {
c = getChar();
} while (!isdigit(c));
do {
res = 10 * res + c - '0';
c = getChar();
} while (isdigit(c));
return res;
}
int getSigned()
{
int res = 0, c;
do {
c = getChar();
} while (!isdigit(c) && c != '-');
int chg = (c == '-');
if (chg) {
c = getChar();
}
do {
res = 10 * res + c - '0';
c = getChar();
} while (isdigit(c));
return chg ? -res : res;
}
long long getInt64()
{
long long res = 0;
int c;
do {
c = getChar();
} while (!isdigit(c));
do {
res = 10 * res + c - '0';
c = getChar();
} while (isdigit(c));
return res;
}
long long getSigned64()
{
long long res = 0;
int c;
do {
c = getChar();
} while (!isdigit(c) && c != '-');
int chg = (c == '-');
if (chg) {
c = getChar();
}
do {
res = 10 * res + c - '0';
c = getChar();
} while (isdigit(c));
return chg ? -res : res;
}
};
class OutParser
{
private:
FILE *f;
char buf[4096];
int stk[19];
int pos;
public:
OutParser(const char* _name)
{
f = fopen(_name, "w");
pos = 0;
}
OutParser(FILE* _f) {
f = _f;
pos = 0;
}
~OutParser() {
fwrite(buf, 1, pos, f);
fclose(f);
}
void putChar(int c)
{
if (pos == 4096) {
fwrite(buf, 1, 4096, f);
pos = 0;
}
buf[pos++] = c;
}
void putInt(int n)
{
if (n < 0) {
putChar('-');
n = -n;
}
if (n == 0) {
putChar('0');
} else {
int l = 0;
while (n) {
stk[l++] = n % 10;
n /= 10;
}
for (int i = l - 1; i >= 0; --i) {
putChar(stk[i] + '0');
}
}
}
void putInt64(long long n)
{
if (n < 0) {
putChar('-');
n = -n;
}
if (n == 0) {
putChar('0');
} else {
int l = 0;
while (n) {
stk[l++] = n % 10;
n /= 10;
}
for (int i = l - 1; l >= 0; --l) {
putChar(stk[i] + '0');
}
}
}
};
#define N_MAX 500000
int v[N_MAX];
void qsort(int b, int e)
{
if (e - b > 1) {
int piv = v[(b + e) / 2];
int l = b - 1, r = e;
while (l < r) {
while (v[++l] < piv);
while (v[--r] > piv);
if (l < r) {
int aux = v[l];
v[l] = v[r];
v[r] = aux;
}
}
qsort(b, l);
qsort(l, e);
}
}
int main()
{
InParser fin("algsort.in");
OutParser fout("algsort.out");
int N = fin.getInt();
for (int i = 0; i < N; ++i) {
v[i] = fin.getSigned();
}
qsort(0, N);
for (int i = 0; i < N; ++i) {
fout.putInt(v[i]);
fout.putChar(' ');
}
return 0;
}