#1136039 (C++17) No.3525 擬奇平方数

• 問題: No.3525 擬奇平方数
• ユーザー: hotman78
• 提出日時: 2025-11-22 16:32:32
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 27 ms / 2,000 ms
• コード長: 3,676 bytes
• コンパイル時間: 2,959 ms
• コンパイル使用メモリ: 247,560 KB
• 実行使用メモリ: 30,320 KB
• 平均クエリ数: 702.05
• 最終ジャッジ日時: 2026-05-01 21:07:16
• 合計ジャッジ時間: 8,620 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

ファイルパターン	結果
other	AC * 60

ソースコード

#line 1 "main.cpp"
#include <bits/stdc++.h>
using namespace std;

int sz2 = 1;
map<string, int> ma;
void query1(string a, string b, string op, string res) {
    assert(ma.count(a));
    assert(ma.count(b));
    cout << "a " << ma[a] << " " << op << " " << ma[b] << endl;
    // cerr<<"a "<<ma[a]<<" "<<op<<" "<<ma[b]<<endl;

    cout << flush;
    ++sz2;
    ma[res] = sz2;
}

bool query2(string a, string b) {
    // cerr<<"? "<<a<<" "<<"<"<<" "<<b<<endl;
    assert(ma.count(a));
    assert(ma.count(b));
    cout << "? " << ma[a] << " " << "<" << " " << ma[b] << endl;
    cout << flush;
    string res;
    cin >> res;
    return res == "T";
}

bool is_equal(string a, string b) { return !query2(a, b) && !query2(b, a); }

int mapping(string s) { return ma[s]; }

int main() {
    // 1
    ma["n"] = 1;
    // N 1 2 3 4 5 6 ... sz
    // 1 4 9 ... sz^2
    // N+1 N+4 ... N+sz^2
    // sqrt(N+1) sqrt(N+4) ... sqrt(N+sz^2)
    int sz = 40;
    // 2~200
    query1("n", "n", "r", "1");
    query1("1", "1", "+", "2");
    query1("2", "1", "+", "3");
    query1("2", "n", "r", "sqrt n");
    query1("sqrt n", "sqrt n", "*", "n2");
    query1("sqrt n", "1", "+", "a_" + to_string(1));
    for (int i = 1; i < sz; ++i) {
        query1("a_" + to_string(i), "1", "+", "a_" + to_string(i + 1));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("a_" + to_string(i), "a_" + to_string(i), "*",
               "power of a_" + to_string(i));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("power of a_" + to_string(i), "n", "-",
               "power of b_" + to_string(i));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("2", "power of b_" + to_string(i), "r", "b_" + to_string(i));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("b_" + to_string(i), "b_" + to_string(i), "*",
               "power of b2_" + to_string(i));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("a_" + to_string(i), "b_" + to_string(i), "-",
               "d_" + to_string(i));
    }
    for (int i = 1; i < sz + 1; ++i) {
        query1("d_" + to_string(i), "3", "*", "3d_" + to_string(i));
        query1("3d_" + to_string(i), "1", "+", "3d+1_" + to_string(i));
        query1("3d+1_" + to_string(i), "n", "*", "(3d+1)n_" + to_string(i));
        query1("d_" + to_string(i), "d_" + to_string(i), "*",
               "d^2_" + to_string(i));
        query1("d^2_" + to_string(i), "d_" + to_string(i), "*",
               "d^3_" + to_string(i));
        query1("(3d+1)n_" + to_string(i), "d^3_" + to_string(i), "+",
               "(3d+1)n+d^3_" + to_string(i));
        query1("(3d+1)n+d^3_" + to_string(i), "(3d+1)n+d^3_" + to_string(i),
               "*", "((3d+1)n+d^3)^2_" + to_string(i));
        query1("d^2_" + to_string(i), "3", "*", "3d^2_" + to_string(i));
        query1("3d^2_" + to_string(i), "n", "+", "n+3d^2_" + to_string(i));
        query1("n+3d^2_" + to_string(i), "n+3d^2_" + to_string(i), "*",
               "(n+3d^2)^2_" + to_string(i));
        query1("(n+3d^2)^2_" + to_string(i), "n", "*",
               "n(n+3d^2)^2_" + to_string(i));
    }
    if (is_equal("n", "n2")) {
        cout << "! Yes" << endl;
        cout << flush;
        // cerr<<"yes"<<endl;
        return 0;
    }
    for (int i = 1; i < sz + 1; ++i) {
        if (query2("((3d+1)n+d^3)^2_" + to_string(i),
                   "n(n+3d^2)^2_" + to_string(i))) {
            break;
        }
        if (is_equal("power of b_" + to_string(i),
                     "power of b2_" + to_string(i))) {
            cout << "! Yes" << endl;
            cout << flush;
            return 0;
        }
    }
    cout << "! No" << endl;
    cout << flush;
}