結果

問題 No.365 ジェンガソート
ユーザー mannshi222mannshi222
提出日時 2019-07-13 20:07:00
言語 C
(gcc 12.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,624 KB
testcase_01 AC 1 ms
7,708 KB
testcase_02 AC 1 ms
10,624 KB
testcase_03 AC 1 ms
7,576 KB
testcase_04 WA -
testcase_05 AC 1 ms
10,624 KB
testcase_06 AC 1 ms
10,624 KB
testcase_07 AC 1 ms
7,424 KB
testcase_08 WA -
testcase_09 AC 1 ms
7,436 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 1 ms
10,624 KB
testcase_15 AC 1 ms
7,296 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 WA -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 WA -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 WA -
testcase_35 TLE -
testcase_36 AC 7 ms
5,248 KB
testcase_37 AC 10 ms
5,248 KB
testcase_38 TLE -
testcase_39 AC 9 ms
5,248 KB
testcase_40 AC 1,632 ms
7,808 KB
権限があれば一括ダウンロードができます

ソースコード

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