zzuli 1812: sort

2215 ワード

http://acm.zzuli.edu.cn/problem.php?id=1812
1812: sort
Description
皆さんはソートに詳しいと思いますが、spyはソートにあまり詳しくないようです.ある日、彼はこのようなソートに関するテーマを見ました.
k個のスペースで区切られた整数については、n 1,n 2...nkの順である.すべての下付き文字が3ではなく、2で割り切れる数をこれらの数字の元の位置に昇順に並べ、また、残りの下付き文字が3で割り切れる数をこれらの数字の元の位置に降順に並べてください.
spyは長い間考えていたが、どのようにソートするか分からないので、彼を助けることができますか?
Input
複数のグループのデータは、各グループのデータの1行につき、k個の1000未満の正の整数であり、n 1,n 2...nkの順である.(1 <= k <= 100000)
Output
データのセットごとに、ソート後の結果が出力されます.
Sample Input
1 3 4 2 10 6 8

Sample Output
1 2 6 3 10 4 8

入力データは1行を占めて、すべて使えません!EOF読み込み、文字読み込み、リターンオフに遭遇した場合終了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
#include <map>

using namespace std;
typedef long long LL;

#define N 110000
#define INF 0x3f3f3f3f
#define PI acos (-1.0)
#define EPS 1e-5
#define met(a, b) memset (a, b, sizeof (a))

int main ()
{
    int b1[N], b2[N], a[N], x;
    while (scanf ("%d", &x) != EOF)
    {
        met (b1, 0);
        met (b2, 0);
        met (a, 0);
        a[1] = x;
        int k = 1;
        char ch;

        while (scanf ("%c", &ch), ch!='
') { if (ch == ' ') k++; if (ch >= '0' && ch <= '9') a[k] = a[k]*10 + ch-'0'; } int j1 = 0, j2 = 0; for (int i=1; i<=k; i++) { if (i%2==0 && i%3) b1[j1++] = a[i]; else if (i%3 == 0) b2[j2++] = a[i]; } sort (b1, b1+j1); sort (b2, b2+j2); j1 = 0, j2--; for (int i=1; i<=k; i++) { if (i%2==0 && i%3) a[i] = b1[j1++]; else if (i%3==0) a[i] = b2[j2--]; } for (int i=1; i<k; i++) printf ("%d ", a[i]); printf ("%d
", a[k]); } return 0; }