aboutsummaryrefslogtreecommitdiff
path: root/20/practice/babynames.cpp
blob: 42a5629d16bd2938db1d1b45f3c8fb27d679bed2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M1 = 8191, M2 = 1e9+7;

string s[10001];
vector<int> h[10001];
int r[10001], hs[2][10001];

inline void print(int x, int d) {
	cout << "MOO ";
	for (int i = 0; i < d; ++i) cout << (1 & (x >> i));
	cout << endl;
}

inline int read(int d) {
	int x = 0;
	for (int i = 0; i < 16; ++i) {
		char c;
		cin >> c;
		if (c == '1') x |= (1 << i);
	}
	return x;
}

inline int hsh(string& s, int m) {
	ll x = 0;
	for (auto& c : s) x *= 31, x += c - 'a', x %= m;
	return x;
}

int main() {
	ofstream debug("debug");

	int c, n[2];
	cin >> c >> n[0];
	for (int i = 0; i < n[0]; ++i) {
		cin >> s[i];
		hs[0][i] = hsh(s[i], M1);
		hs[1][i] = hsh(s[i], M2);
	}
	if (c) {
		print(n[0], 16);
		debug << 1 << ' ' << n[1];
		n[1] = read(16);

		for (int i = 0; i < n[0]; ++i) {
			print(hs[0][i], 13);
			bool b;
			cin >> b;
			if (b == 1) {
				print(hs[1][i], 30);
				cin >> b;
				if (b == 1) {
					cout << "RETURN " << s[i] << endl;
					return 0;
				}
			}
		}
	}
	else {
		n[1] = read(16);
		debug << 0 << ' ' << n[1];
		print(n[0], 16);
		
		for (int i = 0; i < n[0]; ++i) {
			h[hs[0][i]].push_back(i);
		}
		for (int i = 0; i < n[1]; ++i) {
			r[i] = read(13);
			if (h[r[i]].empty()) {
				print(0, 1);
			}
			else {
				print(1, 1);
				int x;
				x = read(30);
				bool ans = 0;
				for (auto& y : h[r[i]]) {
					if (hs[1][y] == x) {
						ans = 1;
						cout << "RETURN " << s[y] << endl;
						print(1, 1);
						return 0;
					}
				}
				if (!ans) {
					print(0, 1);
				}
			}
		}
	}
}