結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー よいちなすの
提出日時 2026-04-18 03:27:39
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 1,950 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,463 ms
コンパイル使用メモリ 348,728 KB
実行使用メモリ 30,320 KB
平均クエリ数 10.47
最終ジャッジ日時 2026-04-18 03:27:49
合計ジャッジ時間 8,666 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

int solve(const string& s, int a, int b, int N) {
    return (s[N - 1 - a] - '0') * (s[N - 1 - b] - '0');
}

int main() {
    int N;
    if (!(cin >> N)) return 0;

    vector<int> p(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cout << "? " << i << " " << N - 1 << endl;
        cin >> p[i];
        if (p[i] == -1) return 0;
    }

    vector<string> ans;
    for (int k = 1; k <= 9; ++k) {
        string s = "";
        bool ok = true;
        for (int i = 0; i < N - 1; ++i) {
            if (p[i] % k == 0 && p[i] / k <= 9) {
                s += to_string(p[i] / k);
            } else {
                ok = false;
                break;
            }
        }
        if (ok) {
            s += to_string(k);
            reverse(s.begin(), s.end()); 
            ans.push_back(s);
        }
    }

    if (ans.size() > 1) {
        int best_a = -1, best_b = -1;
        int max = 0;

        for (int a = 0; a < N; ++a) {
            for (int b = a + 1; b < N; ++b) {
                set<int> X;
                for (const string& s : ans) {
                    X.insert(solve(s, a, b, N));
                }
                if ((int)X.size() > max) {
                    max = X.size();
                    best_a = a;
                    best_b = b;
                }
            }
        }

        if (best_a != -1 && max > 1) {
            cout << "? " << best_a << " " << best_b << endl;
            int p_last;
            cin >> p_last;
            if (p_last == -1) return 0;

            vector<string> next_ans;
            for (const string& s : ans) {
                if (solve(s, best_a, best_b, N) == p_last) {
                    next_ans.push_back(s);
                }
            }
            ans = next_ans;
        }
    }

    
    if (ans.size() == 1) {
        cout << "! " << ans[0] << endl;
    } else {
        cout << "! -1" << endl;
    }

    return 0;
}
0