結果

問題 No.182 新規性の虜
ユーザー nonamae
提出日時 2022-07-29 17:11:58
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
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