結果

問題 No.182 新規性の虜
ユーザー nonamaenonamae
提出日時 2022-07-29 17:11:58
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 1,358 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 30,976 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 08:14:19
合計ジャッジ時間 1,327 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 9 ms
5,376 KB
testcase_09 AC 15 ms
5,376 KB
testcase_10 AC 13 ms
5,376 KB
testcase_11 AC 11 ms
5,376 KB
testcase_12 AC 5 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 10 ms
5,376 KB
testcase_19 AC 8 ms
5,376 KB
testcase_20 AC 6 ms
5,376 KB
testcase_21 AC 13 ms
5,376 KB
testcase_22 AC 7 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 14 ms
5,376 KB
testcase_25 AC 11 ms
5,376 KB
testcase_26 AC 3 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
evil01.txt AC 16 ms
5,376 KB
evil02.txt AC 17 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'radix_sort64':
main.c:15:9: warning: implicit declaration of function 'memset' [-Wimplicit-function-declaration]
   15 |         memset(work2, 0, 0x10000 * sizeof(uint64_t));
      |         ^~~~~~
main.c:4:1: note: include '<string.h>' or provide a declaration of 'memset'
    3 | #include <stdint.h>
  +++ |+#include <string.h>
    4 | 
main.c:15:9: warning: incompatible implicit declaration of built-in function 'memset' [-Wbuiltin-declaration-mismatch]
   15 |         memset(work2, 0, 0x10000 * sizeof(uint64_t));
      |         ^~~~~~
main.c:15:9: note: include '<string.h>' or provide a declaration of 'memset'

ソースコード

diff # 

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

void radix_sort64(uint64_t *a, int a_len) {
    uint64_t *work0 = (uint64_t *)calloc(0x10000, sizeof(uint64_t));
    uint64_t *work1 = (uint64_t *)calloc(a_len, sizeof(uint64_t));
    uint64_t *work2 = (uint64_t *)calloc(0x10000, sizeof(uint64_t));
    #ifdef LOCAL
    if (work0 == NULL || work1 == NULL || work2 == NULL) exit(EXIT_FAILURE);
    #endif
    uint64_t shift = 0;
    __uint128_t x = 0;
    while (shift < 64ul) {
        memset(work2, 0, 0x10000 * sizeof(uint64_t));
        for (int i = 0; i < a_len; i++) {
            x = (a[i] >> shift) & 0xffff;
            work2[x]++;
            work1[i] = a[i];
        }
        work0[0] = 0;
        for (uint64_t u = 0; u < 0xffff; u++) work0[u + 1] = work0[u] + work2[u];
        for (int i = 0; i < a_len; i++) {
            x = (work1[i] >> shift) & 0xffff;
            a[work0[x]] = work1[i];
            work0[x]++;
        }
        shift += 16;
    }
    free(work0);
    free(work1);
    free(work2);
}

int main(void) {
    int n; scanf("%d", &n);
    int64_t a[n + 2];
    for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    a[n] = 0;
    a[n + 1] = 1e9 + 7;
    radix_sort64(a, n + 2);
    int ans = 0;
    for (int i = 1; i <= n; ++i) if (a[i - 1] != a[i] && a[i] != a[i + 1]) ++ans;
    printf("%d\n", ans);
    return 0;
}
0