// BEGIN: main.cpp #line 1 "main.cpp" // BEGIN: my_template.hpp #line 1 "my_template.hpp" #if defined(USE_PCH) #include #else #if defined(__GNUC__) #include #pragma GCC optimize("Ofast,unroll-loops") // 環境によってはコンパイル成功かつ実行時エラー #pragma GCC target("avx2,popcnt") #endif #include #include using namespace std; using ll = long long; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using f128 = __float128; template constexpr bool dependent_false = false; template constexpr T infty = [] { static_assert(dependent_false, "infty is not defined"); return T{}; }(); template <> constexpr int infty = 1'010'000'000; template <> constexpr ll infty = 2'020'000'000'000'000'000; template <> constexpr u32 infty = infty; template <> constexpr u64 infty = infty; template <> constexpr i128 infty = i128(infty) * 2'000'000'000'000'000'000; template <> constexpr double infty = numeric_limits::infinity(); template <> constexpr long double infty = numeric_limits::infinity(); using pi = pair; using vi = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using pq_max = priority_queue; template using pq_min = priority_queue, greater>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) // https://trap.jp/post/1224/ #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c)) #define FOR1_R(a) for (ll i = ll(a) - 1; i >= ll(0); --i) #define FOR2_R(i, a) for (ll i = ll(a) - 1; i >= ll(0); --i) #define FOR3_R(i, a, b) for (ll i = ll(b) - 1; i >= ll(a); --i) #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define stoi stoll // require y > 0 template T floor(T x, T y) { return x / y - (x % y < 0); } // require y > 0 template T ceil(T x, T y) { return (x / y) + (x % y > 0); } // require y > 0 template T bmod(T x, T y) { T r = x % y; return (r < 0 ? r + y : r); } // require y > 0 template pair divmod(T x, T y) { T q = x / y, r = x % y; if (r < 0) --q, r += y; return {q, r}; } constexpr auto TEN = [] { array A{}; A[0] = 1; for (int i = 1; i < 20; ++i) A[i] = 10 * A[i - 1]; return A; }(); template T SUM(const U &A) { return std::accumulate(A.begin(), A.end(), T{}); } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) template inline long long LB(const C &c, const T &x) { return lower_bound(c.begin(), c.end(), x) - c.begin(); } template inline long long UB(const C &c, const T &x) { return upper_bound(c.begin(), c.end(), x) - c.begin(); } #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()) template T POP(deque &que) { T a = que.front(); que.pop_front(); return a; } template T POP(priority_queue &que) { T a = que.top(); que.pop(); return a; } template T POP(vc &que) { T a = que.back(); que.pop_back(); return a; } template ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (1) { ll x = (ok + ng) / 2; if (x == ok || x == ng) break; (check(x) ? ok : ng) = x; } return ok; } template double binary_search_real(F check, double ok, double ng, int iter = 100) { FOR(iter) { double x = (ok + ng) / 2; (check(x) ? ok : ng) = x; } return (ok + ng) / 2; } template inline bool chmax(T &a, const S &b) { T c = max(a, b); bool changed = (c != a); a = c; return changed; } template inline bool chmin(T &a, const S &b) { T c = min(a, b); bool changed = (c != a); a = c; return changed; } // ? は -1 vc s_to_vi(const string &S, char first_char) { vc A(S.size()); FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); } return A; } template vc cumsum(const vc &A, int off = 1) { int N = A.size(); vc B(N + 1); FOR(i, N) { B[i + 1] = B[i] + A[i]; } if (off == 0) B.erase(B.begin()); return B; } // stable sort template vc argsort(const vc &A) { vc ids(len(A)); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ids; } // A[I[0]], A[I[1]], ... template vc rearrange(const vc &A, const vc &I) { vc B(len(I)); FOR(i, len(I)) B[i] = A[I[i]]; return B; } template void concat(vc &first, const Vectors &...others) { first.reserve(first.size() + (others.size() + ... + 0)); (first.insert(first.end(), others.begin(), others.end()), ...); } // i128 template , int> = 0> constexpr i128 abs(T x) { return x < 0 ? -x : x; } constexpr i128 gcd(i128 a, i128 b) { while (b != 0) { i128 c = a % b; a = b, b = c; } return abs(a); } #endif // END: my_template.hpp #line 2 "main.cpp" // BEGIN: other/io2.hpp #line 1 "other/io2.hpp" #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ long double __VA_ARGS__; \ IN(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ read(name) void read(int &a) { cin >> a; } void read(long long &a) { cin >> a; } void read(char &a) { cin >> a; } void read(double &a) { cin >> a; } void read(long double &a) { cin >> a; } void read(string &a) { cin >> a; } template void read(pair &p) { read(p.first), read(p.second); } template void read(vector &a) { for (auto &i : a) read(i); } template void read(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &...tail) { read(head); IN(tail...); } template ostream &operator<<(ostream &os, const pair &A) { os << A.fi << " " << A.se; return os; } template ostream &operator<<(ostream &os, const vector &A) { for (size_t i = 0; i < A.size(); i++) { if (i) os << " "; os << A[i]; } return os; } class CoutInitializer { public: CoutInitializer() { std::cout << std::fixed << std::setprecision(15); } }; static CoutInitializer cout_initializer; void print() { cout << "\n"; cout.flush(); } template void print(Head &&head, Tail &&...tail) { cout << head; if (sizeof...(Tail)) cout << " "; print(forward(tail)...); } #if defined(LOCAL) template inline void _show_pack(const char *func, int line, const char *names, Ts &&...args) { // [DEBUG] solve:123 のように先頭に出す cout << "[DEBUG " << func << ':' << line << "] "; const char *p = names; bool first = true; auto next_token = [&]() -> std::pair { while (*p == ' ' || *p == ',') ++p; const char *l = p; while (*p && *p != ',') ++p; const char *r = p; return {l, r}; }; ( [&] { auto [l, r] = next_token(); while (r > l && r[-1] == ' ') --r; if (!first) cout << ' '; first = false; std::string name(l, r); cout << name << " = " << args; }(), ...); print(); } #define SHOW(...) _show_pack(__func__, __LINE__, #__VA_ARGS__, __VA_ARGS__) #else #define SHOW(...) #endif void YES(bool t = 1) { print(t ? "YES" : "NO"); } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void No(bool t = 1) { Yes(!t); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void no(bool t = 1) { yes(!t); } // END: other/io2.hpp #line 3 "main.cpp" void solve() { STR(name); INT(Q); INT(N, M); // 自分は N if (name == "Bob") swap(N, M); VEC(int, A, N); sort(all(A)); auto out = [&](int i) -> int { print("share", 1 + i); INT(x); return x; }; auto ans = [&](int x) -> void { print("answer", x); }; int L = 0, R = N; while (1) { while (N + 2 < M) { M -= 2; } while (N + 2 > M) { N -= 2; L++, --R; } if (N + M <= 3) break; int k = -1; if (N % 2 == 1) k = N / 2; if (M % 2 == 1) k = M / 2; int x = A[k]; int y = out(L + k); if (x == y) return ans(x); int kk = min(N, M) / 2; if (x < y) { L += kk; N -= kk, M -= kk; } else { R -= kk; N -= kk, M -= kk; } // if (N % 2 == 0 && M == N + 1) { // if (x < y) { // L += k; // N -= k, M -= k; // } else { // R -= k; // N -= k, M -= k; // } // continue; // } // if (N % 2 == 0 && N == M + 1) { // if (x < y) { // L += k; // N -= k, M -= k; // } else { // R -= k; // N -= k, M -= k; // } // continue; // } // if (N % 2 == 1 && N + 1 == M) { // if (x < y) { // L += k; // N -= k, M -= k; // } else { // R -= k; // N -= k, M -= k; // } // continue; // } } if (N == 1 && M == 0) { // 渡す必要はあるな out(L); return ans(A[L]); } if (N == 0 && M == 1) { return ans(out(L)); } if (N == 1 && M == 2) { int x = A[L]; int y = out(L); if (x <= y) { return ans(y); } int z = out(L); return ans(min(x, z)); } if (N == 2 && M == 1) { int y = A[L]; int x = out(L); if (x <= y) { return ans(y); } int z = A[L + 1]; out(L + 1); return ans(min(x, z)); } } signed main() { solve(); } // END: main.cpp