結果

問題 No.182 新規性の虜
コンテスト
ユーザー nonamae
提出日時 2022-07-29 17:11:58
言語 C11(gcc12 gnu拡張)
(gcc 12.4.0)
コンパイル:
gcc-12 -O2 -std=gnu11 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,358 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 103 ms
コンパイル使用メモリ 33,452 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:31:28
合計ジャッジ時間 1,038 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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’
main.c: In function ‘main’:
main.c:38:43: warning: format ‘%lld’ expects argument of type ‘long long int *’, but argument 2 has type ‘int64_t *’ {aka ‘long int *’} [-Wformat=]
   38 |     for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
      |                                        ~~~^   ~~~~~
      |                                           |   |
      |                                           |   int64_t * {aka long int *}
      |                                           long long int *
      |                                        %ld
main.c:36:12: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |     int n; scanf("%d", &n);
      |            ^~~~~~~~~~~~~~~
main.c:38:33: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
      |                                 ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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