結果
問題 | No.2061 XOR Sort |
ユーザー |
![]() |
提出日時 | 2022-08-26 23:04:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 318 ms / 2,000 ms |
コード長 | 1,066 bytes |
コンパイル時間 | 4,759 ms |
コンパイル使用メモリ | 255,784 KB |
最終ジャッジ日時 | 2025-01-31 05:31:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; int main(){ // 部分ソートしたいのにPythonではキツイ // 我々は C++ に吸い寄せられてしまうのか? int N; cin >> N; vector<int> a(N); for (int i=0; i<N; i++){ cin >> a[i]; } int tuyosa = 0; vector<int> kugiri={N}; for (int num=30; num>=0; num--){ int pivot = 0; bool kawaru = false; vector<int> newkugiri = kugiri; for (int j: kugiri){ sort(a.begin()+pivot, a.begin()+j, [&num](int x, int y) -> int { if ((x>>num) < (y>>num)) return true; if ((x>>num) > (y>>num)) return false; return x < y; }); int mode = a[pivot] >> num; while (pivot < j){ int targ = a[pivot] >> num; if (targ != mode){ kawaru = true; newkugiri.push_back(pivot); } mode = targ; pivot++; } } sort(newkugiri.begin(), newkugiri.end()); kugiri = newkugiri; if (kawaru){ tuyosa++; } } cout << mint(2).pow(tuyosa).val() << endl; }