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

• 問題: No.3525 擬奇平方数
• ユーザー: hotman78
• 提出日時: 2025-11-22 17:44:19
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 37 ms / 2,000 ms
• コード長: 4,272 bytes
• コンパイル時間: 2,838 ms
• コンパイル使用メモリ: 239,928 KB
• 実行使用メモリ: 30,176 KB
• 平均クエリ数: 336.05
• 最終ジャッジ日時: 2026-05-01 21:07:27
• 合計ジャッジ時間: 9,413 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_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");
    for(long long i=2;i<(1<<30);i*=2){
        query1(to_string(i), to_string(i), "+", to_string(i*2));
    }
    
    query1("2", "n", "r", "sqrt n");
    query1( "n",to_string(1<<20),"*", "2^20n");
    query1( "n",to_string(1<<30),"*", "2^30n");
    query1("2","2^20n","r","1024sqrt n");
    query1("3","2^30n","r","1024cbrt n");
    query1("1024sqrt n", "1024cbrt n", "-", "1024(sqrt n-cbrt 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("d_" + to_string(i), "1024", "*", "1024d_" + 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("1024d_"+to_string(i),"1024(sqrt n-cbrt n)")){
            break;
        }
        // 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;
}