結果

問題 No.2925 2-Letter Shiritori
コンテスト
ユーザー 👑 loop0919
提出日時 2024-09-13 16:58:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 2,699 bytes
コンパイル時間 1,391 ms
コンパイル使用メモリ 108,776 KB
実行使用メモリ 25,452 KB
平均クエリ数 26.00
最終ジャッジ日時 2024-10-12 14:00:57
合計ジャッジ時間 2,976 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
using namespace std;

int main() {
    char alpha;
    cin >> alpha;
    cin.ignore(); // Consume any remaining newline character

    // Initialize used strings
    set<string> used_strings;

    // Initialize all possible strings starting with each letter
    map<char, set<string>> strings_starting_with;
    for (char c1 = 'a'; c1 <= 'z'; ++c1) {
        for (char c2 = 'a'; c2 <= 'z'; ++c2) {
            string s;
            s += c1;
            s += c2;
            strings_starting_with[c1].insert(s);
        }
    }

    // Our initial move
    string first_move;
    first_move += alpha;
    first_move += alpha;
    cout << "? " << first_move << endl;
    used_strings.insert(first_move);
    strings_starting_with[alpha].erase(first_move);

    while (true) {
        string judge_output;
        getline(cin, judge_output);

        if (judge_output == "! WIN" || judge_output == "! LOSE") {
            // Game over
            break;
        }

        if (judge_output.substr(0, 2) == "? ") {
            string T = judge_output.substr(2);
            // Add T to used strings
            used_strings.insert(T);
            strings_starting_with[T[0]].erase(T);

            // Our turn
            char c = T[1]; // Second character of T

            // Try to use c followed by alpha
            string our_move;
            our_move += c;
            our_move += alpha;

            if (used_strings.find(our_move) == used_strings.end()) {
                // Our desired move is unused
            } else {
                // Find any unused string starting with c
                if (strings_starting_with[c].empty()) {
                    // No moves left, but according to the problem, we should always be able to move
                    // However, to be safe, we can output any valid move

                    // But since the first player can always win, this should not happen
                    // To be safe, let's pick any unused string starting with c
                    cout << "! LOSE" << endl;
                    break;
                } else {
                    // Get any unused string starting with c
                    our_move = *strings_starting_with[c].begin();
                }
            }

            // Output our move
            cout << "? " << our_move << endl;
            cout.flush();

            // Add our move to used strings
            used_strings.insert(our_move);
            strings_starting_with[our_move[0]].erase(our_move);
        } else {
            // Unexpected output from judge
            break;
        }
    }

    return 0;
}
0