結果

問題 No.365 ジェンガソート
コンテスト
ユーザー mannshi222
提出日時 2019-07-13 20:07:00
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,630 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-11-22 11:37:50
合計ジャッジ時間 51,551 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 13 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

#define ENDD '\0'
#define KIGY '\n'

int compare_int(const void *a, const void *b);

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}


int main()
{
        int ch;
        char buff[100000+1];
        int buffi;
        int N;
        int *jen;
        int *jennext;
        int jeni;

        buffi = 0;
        while( (ch=getc(stdin)) != KIGY) {
                buff[buffi++] = ch;
        }
        buff[buffi] = ENDD;
        N = atoi(buff);

        buffi=0;
        jeni=0;
        jen = (int *)malloc((sizeof(int))*N);
        while( (ch=getc(stdin)) != EOF) {
                        if( ch==' ' ||  ch==KIGY   ) {
                                buff[buffi] = ENDD;
                                jen[jeni++] = atoi(buff);
                                buffi = 0;
                        }
                        else {
                                buff[buffi++] = ch;
                        }
        }

        /* search max */
        int smax;
        int count  = 0;
        for( smax = N; smax >= 1; smax-- ) {
                /* 一番数字が大きいものを探す */

                /* 探す対象が１の場合、ソートの必要がないので終わり */
                if( smax==1 ) {
                        break;
                }

                /* 一番数字が大きいものを探す */
                jeni = smax-1;
                while( jen[jeni] != smax ){
                        jeni--;
                }

                /* 一番右側に一番大きい数字がある場合 */
                if( jeni == smax-1 ) {
                        continue;
                }

                /* 一番右側にない場合 */
                count += smax-jeni-1;
                /* 次に大きい数字を探す */

                /* 一番大きいものより右側にある数字をソートする */
                qsort(jen+jeni+1, smax-jeni-1, sizeof(int), compare_int);

                /* ソート後の結果を新しい配列左側に移動する */
                jennext = (int *)malloc((sizeof(int))*smax-1);
                int i;
                for( i = 0; i < smax-jeni-1; i++ ) {
                        jennext[i] =jen[jeni+1+i];
                }
                /* 一番大きい数字より左がにあったものを移動する */
                for( int j = 0; j <= jeni-1; j++ ) {
                        jennext[i++] = jen[j];
                }

                free( jen );
                jen = jennext;

        }
        printf("%d\n", count );

        return 0;
}
0