結果
問題 | No.1957 Xor Min |
ユーザー |
![]() |
提出日時 | 2022-05-27 21:39:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,878 bytes |
コンパイル時間 | 1,473 ms |
コンパイル使用メモリ | 173,856 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 15:36:36 |
合計ジャッジ時間 | 2,286 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int A, B;cin >> A >> B;vector<int> a(30), b(30);for (int i = 0; i < 30; i++){a[i] = A >> i & 1;b[i] = B >> i & 1;}int tv = 0, fv = 1000000001;while (fv - tv > 1){int mid = (tv + fv) / 2;vector<int> k(30);for (int i = 0; i < 30; i++){k[i] = mid >> i & 1;}vector<vector<bool>> dp(31, vector<bool>(32, 0));dp[30][0] = true;for (int i = 29; i >= 0; i--){for (int j = 0; j < 32; j++){if (dp[i + 1][j]){for (int x = 0; x < 2; x++){for (int y = 0; y < 2; y++){bool ok = true;int j2 = j;if ((j & 1) == 0 && k[i] == 1 && x == 0){ok = false;} else if (k[i] == 0 && x == 1){j2 |= 1;}if ((j & 2) == 0 && k[i] == 1 && y == 0){ok = false;} else if (k[i] == 0 && y == 1){j2 |= 2;}if ((j & 4) == 0 && k[i] == 1 && (x ^ y) == 0){ok = false;} else if (k[i] == 0 && (x ^ y) == 1){j2 |= 4;}if ((j & 8) == 0 && x == 1 && a[i] == 0){ok = false;} else if (x == 0 && a[i] == 1){j2 |= 8;}if ((j & 16) == 0 && y == 1 && b[i] == 0){ok = false;} else if (y == 0 && b[i] == 1){j2 |= 16;}if (ok){dp[i][j2] = true;}}}}}}bool ok = false;for (int i = 0; i < 32; i++){if (dp[0][i]){ok = true;}}if (ok){tv = mid;} else {fv = mid;}}cout << tv << endl;}