#168909 (C++14) No.130 XOR Minimax

• 問題: No.130 XOR Minimax
• ユーザー: fine
• 提出日時: 2017-04-28 00:12:09
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,048 bytes
• コンパイル時間: 1,957 ms
• コンパイル使用メモリ: 168,200 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-13 14:56:54
• 合計ジャッジ時間: 4,365 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	19 ms; 5,376 KB
testcase_05	WA	-
testcase_06	AC	127 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	16 ms; 5,376 KB
testcase_10	AC	23 ms; 5,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	62 ms; 5,376 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-

ソースコード

#include <bits/stdc++.h>

using namespace std;

int memo[30];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int ng = -1, ok = (1 << 30) - 1;
	int max_d = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 29; j >= 0; j--) {
			if (a[i] >= (1 << j)) {
				max_d = max(max_d, j);
				break;
			}
		}
	}
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		fill_n(memo, 30, -1);
		bool flag = true;
		for (int i = 0; i < n; i++) {
			int tmp = a[i];
			for (int j = max_d; j >= 0; j--) {
				if (memo[j] != -1) {
					tmp ^= (memo[j] << j);
				} else {
					bool flag1 = (tmp > mid);
					bool flag2 = ((tmp ^ (1 << j)) > mid);
					if (flag1) {
						if (flag2) {
							flag = false;
							break;
						} else {
							memo[j] = 1;
							tmp ^= (1 << j);							
						}
					} else if (flag2) {
						memo[j] = 0;
					}
				}
			}
			flag &= (tmp <= mid);
			if (!flag) break;
		}
		if (flag) ok = mid;
		else ng = mid;
	}
	cout << ok << endl;
	return 0;
}