結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー Enderaoe Lyther
提出日時 2026-04-17 21:17:09
言語 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
結果
WA  
実行時間 -
コード長 2,957 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,950 ms
コンパイル使用メモリ 175,592 KB
実行使用メモリ 30,076 KB
平均クエリ数 10.47
最終ジャッジ日時 2026-04-17 21:17:28
合計ジャッジ時間 14,501 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 62 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <set>
#include <string>
#include <vector>

static int dig(const std::string &w, int N, int pos) {
    return w[static_cast<size_t>(N - 1 - pos)] - '0';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    if (!(std::cin >> N)) return 0;
    std::vector<int> p(static_cast<size_t>(N - 1));
    for (int i = 1; i < N; ++i) {
        std::cout << "? 0 " << i << '\n';
        std::cout.flush();
        long long r;
        std::cin >> r;
        if (r == -1) return 0;
        p[static_cast<size_t>(i - 1)] = static_cast<int>(r);
    }

    bool allZero = true;
    for (int x : p)
        if (x != 0) allZero = false;

    if (allZero) {
        std::cout << "! -1\n";
        std::cout.flush();
        return 0;
    }

    std::set<std::string> cand;
    for (int t = 1; t <= 9; ++t) {
        std::vector<int> d(static_cast<size_t>(N));
        d[0] = t;
        bool ok = true;
        for (int i = 1; i < N; ++i) {
            int pr = p[static_cast<size_t>(i - 1)];
            if (pr % t != 0) {
                ok = false;
                break;
            }
            d[static_cast<size_t>(i)] = pr / t;
            if (d[static_cast<size_t>(i)] < 0 || d[static_cast<size_t>(i)] > 9) {
                ok = false;
                break;
            }
        }
        if (!ok) continue;
        if (d[static_cast<size_t>(N - 1)] == 0) continue;
        std::string s;
        s.reserve(static_cast<size_t>(N));
        for (int i = N - 1; i >= 0; --i)
            s.push_back(static_cast<char>('0' + d[static_cast<size_t>(i)]));
        cand.insert(std::move(s));
    }

    if (cand.size() > 1) {
        int sepA = -1, sepB = -1;
        for (int a = 1; a < N; ++a) {
            for (int b = a + 1; b < N; ++b) {
                int v0 = -1;
                bool diff = false;
                for (const std::string &w : cand) {
                    int pr = dig(w, N, a) * dig(w, N, b);
                    if (v0 < 0) v0 = pr;
                    else if (pr != v0) {
                        diff = true;
                        break;
                    }
                }
                if (diff) {
                    sepA = a;
                    sepB = b;
                    break;
                }
            }
            if (sepA >= 0) break;
        }
        if (sepA >= 0) {
            std::cout << "? " << sepA << " " << sepB << '\n';
            std::cout.flush();
            long long r;
            std::cin >> r;
            if (r == -1) return 0;
            std::set<std::string> nxt;
            for (const std::string &w : cand) {
                if (dig(w, N, sepA) * dig(w, N, sepB) == r) nxt.insert(w);
            }
            cand = std::move(nxt);
        }
    }

    if (cand.size() == 1) {
        std::cout << "! " << *cand.begin() << '\n';
    } else {
        std::cout << "! -1\n";
    }
    std::cout.flush();
    return 0;
}
0