結果
問題 | No.2061 XOR Sort |
ユーザー |
![]() |
提出日時 | 2022-08-26 22:38:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 951 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 33,408 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 23:16:27 |
合計ジャッジ時間 | 1,881 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <cstdio>int readint() {int res = 0;char c = getchar_unlocked();while ('0' <= c && c <= '9') {res = res * 10 + int(c - '0');c = getchar_unlocked();}return res;}int N, A[200000], tmp[200000], cnt[32800];int main() {// step #1. input & radix sortN = readint();for (int i = 0; i < N; i++) {A[i] = readint();cnt[(A[i] & 32767) + 1] += 1;}for (int i = 0; i < 32768; i++) cnt[i + 1] += cnt[i];for (int i = 0; i < N; i++) tmp[cnt[A[i] & 32767]++] = A[i];for (int i = 0; i < 32769; i++) cnt[i] = 0;for (int i = 0; i < N; i++) cnt[(tmp[i] >> 15) + 1] += 1;for (int i = 0; i < 32768; i++) cnt[i + 1] += cnt[i];for (int i = 0; i < N; i++) A[cnt[tmp[i] >> 15]++] = tmp[i];// step #2. compute the answerint bit = 0;for (int i = 0; i < N - 1; i++) {if (A[i] != A[i + 1]) {bit |= 1 << __builtin_clz(A[i] ^ A[i + 1]);}}printf("%d\n", (1 << __builtin_popcount(bit)) % 998244353);return 0;}