結果
問題 | No.1969 XOR Equation |
ユーザー |
👑 ![]() |
提出日時 | 2022-06-03 21:56:56 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 2,101 bytes |
コンパイル時間 | 3,579 ms |
コンパイル使用メモリ | 124,472 KB |
最終ジャッジ日時 | 2025-01-29 17:41:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using modint = atcoder::static_modint<998244353>;void testcase(){int N; cin >> N;u64 Y; cin >> Y;vector<u64> A(N); rep(i,N) cin >> A[i];vector<u64> B = A;const u64 IMPOSSIBLE = ~(u64)0;vector<u64> dp = {0};rep(d,61){u64 lowerBit1 = ((u64)1 << d) - 1;u64 lowerBit = ((u64)1 << (d + 1)) - 1;auto cmpByLowerBit1 = [lowerBit1](u64 l, u64 r) -> bool { return (l & lowerBit1) < (r & lowerBit1); };auto cmpByLowerBit = [lowerBit](u64 l, u64 r) -> bool { return (l & lowerBit) < (r & lowerBit); };sort(A.begin(), A.end(), cmpByLowerBit1);sort(B.begin(), B.end(), cmpByLowerBit);vector<u64> tmp(N + 1, IMPOSSIBLE);int rawcnt = 0;for(u64 a : A) if(a & ((u64)1 << d)) rawcnt ^= 1;int tgcnt = (Y >> d) & 1;for(u64 x : dp){int p = A.end() - lower_bound(A.begin(), A.end(), ((u64)1 << d) - x, cmpByLowerBit1);if(x == 0) p = 0;rep(t,2) if(d != 60 || t == 0){u64 nx = x | ((u64)t << d);int q = p & 1;if((rawcnt ^ q ^ ((t*N)&1)) != tgcnt) continue;int pp = B.end() - lower_bound(B.begin(), B.end(), ((u64)1 << (d + 1)) - nx, cmpByLowerBit);if(nx == 0) pp = 0;tmp[pp] = min(tmp[pp], nx);}}dp.clear();for(u64 x : tmp) if(x != IMPOSSIBLE) dp.push_back(x);}u64 ans = IMPOSSIBLE;for(auto a : dp) ans = min(ans, a);cout << (i64)ans << '\n';}int main(){int T; cin >> T;while(T --> 0) testcase();return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;