結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー sig_256
提出日時 2026-04-28 22:49:11
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 1,106 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,491 ms
コンパイル使用メモリ 86,404 KB
実行使用メモリ 30,308 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-28 22:49:20
合計ジャッジ時間 7,148 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cmath>

int N;

int q(int a, int b) {
	if (a < b) std::swap(a, b);
	int p;
	std::cout << "? " << N - a - 1 << ' ' << N - b - 1 << std::endl;
	std::cin >> p;
	return p;
}

int main() {
	std::cin >> N;
	std::vector<int> d(N);
	int i = 0, i2 = -1, i3 = -1, p1, p2, p3;
	while(++i < N) {
		p3 = q(0, i);
		if (p3 != 0) {
			i2 = i;
			break;
		}
		d[i] = 0;
	}
	while(++i < N) {
		p2 = q(0, i);
		if (p2 != 0) {
			i3 = i;
			break;
		}
		d[i] = 0;
	}
	if (i3 == -1) {
		std::cout << "! ";
		if (i2 == -1) {
			std::cout << -1;
		} else {
			int r = sqrt(p3);
			if (r * r == p3 && (r == 1 || r == 5 || r == 7 || r == 8 || r == 9)) {
				d[0] = d[i2] = r;
				for (i = 0; i < N; ++i) {
					std::cout << d[i];
				}
			} else {
				std::cout << -1;
			}
		}
		std::cout << std::endl;
		return 0;
	}
	p1 = q(i2, i3);
	d[0] =  std::sqrt(p2 * p3 / p1);
	d[i2] = std::sqrt(p3 * p1 / p2);
	d[i3] = std::sqrt(p1 * p2 / p3);
	while(++i < N) {
		d[i] = q(0, i) / d[0];
	}
	std::cout << "! ";
	for (i = 0; i < N; ++i) {
		std::cout << d[i];
	}
	std::cout << std::endl;
}
0