QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#423647	#8719. 后继	huabin	WA	72ms	3860kb	C++23	4.7kb	2024-05-28 14:25:51	2024-05-28 14:25:51

Judging History

你现在查看的是最新测评结果

[2024-05-28 14:25:51]
评测

测评结果：WA
用时：72ms
内存：3860kb

查看

[2024-05-28 14:25:51]
提交

answer

#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <set>
#include <string>
#include <tuple>
#include <vector>

namespace cave {
template <typename T> int len(const T &x) { return (int)x.size(); }
template <typename T, int S> int len(const T (&)[S]) { return S; }
[[maybe_unused]] static inline constexpr struct __MAX_Kind {
	constexpr __MAX_Kind() {}
	__MAX_Kind(const __MAX_Kind &&) = delete;
	__MAX_Kind(const __MAX_Kind &) = delete;
	__MAX_Kind &operator=(const __MAX_Kind &&) = delete;
	__MAX_Kind &operator=(const __MAX_Kind &) = delete;
	template <typename T> constexpr operator T() const { return std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator==(T x) const { return x == std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator!=(T x) const { return x != std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator<(T x) const { return x < std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator<=(T x) const { return x <= std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator>(T x) const { return x > std::numeric_limits<T>::max(); }
	template <typename T> constexpr bool operator>=(T x) const { return x >= std::numeric_limits<T>::max(); }
} MAX;
[[maybe_unused]] static inline constexpr struct __MIN_Kind {
	constexpr __MIN_Kind() {}
	__MIN_Kind(const __MIN_Kind &&) = delete;
	__MIN_Kind(const __MIN_Kind &) = delete;
	__MIN_Kind &operator=(const __MIN_Kind &&) = delete;
	__MIN_Kind &operator=(const __MIN_Kind &) = delete;
	template <typename T> constexpr operator T() const { return std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator==(T x) const { return x == std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator!=(T x) const { return x != std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator<(T x) const { return x < std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator<=(T x) const { return x <= std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator>(T x) const { return x > std::numeric_limits<T>::min(); }
	template <typename T> constexpr bool operator>=(T x) const { return x >= std::numeric_limits<T>::min(); }
} MIN;
} // namespace cave

using ll = long long;
using namespace std;
using Byte = signed char;
using namespace cave;

static void solve(void);

int main(void) {
	// cin.tie(nullptr), cout.tie(nullptr);
	// ios::sync_with_stdio(false);

	ll t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

struct Node {
	int depth;
	int value;
	int child[2];
	int tin, tout;
};

static void insert(int item, int value, vector<Node> &nodes) {
	int p = 0;
	for (int i = 0; i < 30; i++) {
		int bit = !!(item & (1 << (29 - i)));
		if (nodes[p].child[bit] == -1) {
			nodes[p].child[bit] = nodes.size();
			nodes.push_back({nodes[p].depth + 1, -1, {-1, -1}, -1, -1});
		}
		p = nodes[p].child[bit];
	}
	nodes[p].value = value;
}

static int subtree_max(int p, int mask, const vector<Node> &nodes) {
	while (nodes[p].depth != 30) {
		int bit = !(mask & (1 << (29 - nodes[p].depth)));
		if (nodes[p].child[bit] != -1) {
			p = nodes[p].child[bit];
		} else if (nodes[p].child[!bit] != -1) {
			p = nodes[p].child[!bit];
		}
	}
	return nodes[p].value;
}

static bool in_subtree(int p, int t, const vector<Node> &nodes) { return nodes[p].tin <= t && t <= nodes[p].tout; }

static void dfs(int p, int &t, vector<Node> &nodes) {
	nodes[p].tin = t++;
	if (nodes[p].child[0] != -1) {
		dfs(nodes[p].child[0], t, nodes);
	}
	if (nodes[p].child[1] != -1) {
		dfs(nodes[p].child[1], t, nodes);
	}
	nodes[p].tout = t++;
}

static void solve(void) {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	vector<Node> trie = {{0, -1, {-1, -1}, -1, -1}};
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		insert(a[i], i, trie);
	}
	vector<vector<int>> depth_map(30);
	for (int i = 1; i < len(trie); i++) {
		if (trie[i].child[0] != -1 && trie[i].child[1] != -1) {
			depth_map[29 - trie[i].depth].push_back(i);
		}
	}
	int t = 0;
	dfs(0, t, trie);
	vector<int> t_table(n);
	for (int i = 0; i < len(trie); i++) {
		if (trie[i].value != -1) {
			t_table[trie[i].value] = trie[i].tin;
		}
	}
	while (m--) {
		int mask = 0;
		for (int i = 0; i < 30; i++) {
			if (!depth_map[i].empty()) {
				int p = depth_map[i][0];
				cout << "? " << subtree_max(p, mask, trie) + 1 << endl;
				int value;
				cin >> value;
				mask |= (1 << i) * (value > 0 && in_subtree(p, t_table[value - 1], trie));
			}
		}
		cout << "! " << mask << endl;
	}
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3688kb

input:

output:

? 3
? 2
? 4
! 3

result:

ok 1 number(s): "3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3860kb

input:

1 1
0

output:

! 0

result:

ok 1 number(s): "0"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3576kb

input:

10 10
380864879 387438357 21484978 21099484 375657510 23189485 24467021 379687119 386094773 15156199
-1
8
4
2
10
10
10
8
4
5
1
7
4
8
10
3
5
3
4
8
-1
5
10
10
10
8
4
5
1
-1
10
8
4
5
1
-1
6
5
10
5
8
4
4
8
-1
5
10
10
4
9
-1
9
10
10
8
5
4
5
-1
-1

output:

? 3
? 1
? 6
? 8
? 9
? 9
! 271581184
? 3
? 1
? 6
? 8
? 9
? 5
! 296747008
? 3
? 1
? 6
? 8
? 9
? 8
! 286523392
? 3
? 1
? 6
? 8
? 9
? 9
! 278134784
? 3
? 1
? 6
? 8
? 9
? 5
! 28311552
? 3
? 1
? 6
? 8
? 9
? 5
! 28311552
? 3
? 1
? 7
? 1
? 2
? 5
! 293601280
? 3
? 1
? 6
? 8
? 9
? 9
! 278134784
? 3
? 1
? 7
? ...

result:

ok 10 numbers

Test #4:

score: -100

Wrong Answer

time: 72ms

memory: 3752kb

input:

100 3000
416322873 449728250 688705913 946343465 16202884 153238658 573284215 724198910 577719053 868106680 951494055 942341618 190594266 331719623 856324110 977865755 151782935 163752541 1565918 870244322 299691610 37854919 198293342 152446496 549402023 869857831 869628458 573984494 162791133 94423...

output:

? 97
? 57
? 50
? 60
? 4
? 50
? 64
? 1
? 67
? 53
? 78
? 41
! 184027136
? 97
? 57
? 50
? 60
? 4
? 50
? 64
? 1
? 1
? 53
? 78
? 41
! 445644800
? 97
? 57
? 50
? 60
? 4
? 88
? 48
? 1
? 1
? 53
? 53
? 70
! 145555456
? 97
? 57
? 50
? 60
? 4
? 88
? 64
? 1
? 1
? 53
? 78
? 41
! 179914752
? 97
? 57
? 50
? 60
? 4...

result:

wrong answer 5th numbers differ - expected: '543703040', found: '6832128'