結果
| 問題 | No.3501 Digit Products 2 |
| コンテスト | |
| ユーザー |
 zer0-star
|
| 提出日時 | 2026-04-17 23:50:27 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,007 bytes |
| 記録 | |
| コンパイル時間 | 10,017 ms |
| コンパイル使用メモリ | 461,004 KB |
| 実行使用メモリ | 30,308 KB |
| 平均クエリ数 | 10.74 |
| 最終ジャッジ日時 | 2026-04-17 23:50:53 |
| 合計ジャッジ時間 | 23,256 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 62 WA * 10 |
ソースコード
#define USE_ACLIBRARY 0
#if __has_include("all.hpp") && 0
#include "all.hpp"
#else
#include <bits/extc++.h>
#if __has_include(<atcoder/all>) || USE_ACLIBRARY
#include <atcoder/all>
#endif
#endif
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
using ll = long long int;
using ull = unsigned long long int;
using pll = std::pair<ll, ll>;
using pil = std::pair<int, ll>;
using pli = std::pair<ll, int>;
using pii = std::pair<int, int>;
using namespace std::literals;
std::mt19937_64 rng{std::random_device()()};
template <class T>
bool chmin(T& x, const T& val) {
if (x > val) {
x = val;
return true;
} else {
return false;
}
}
template <class T>
bool chmin2(T& x, const T& val) {
if (x < 0 || x > val) {
x = val;
return true;
} else {
return false;
}
}
template <class T>
bool chmax(T& x, const T& val) {
if (x < val) {
x = val;
return true;
} else {
return false;
}
}
ll isqrt(ll n) {
assert(n >= 0);
if (n == 0) return 0;
uint32_t c = (std::bit_width(uint64_t(n)) - 1) / 2;
ll a = 1;
ll d = 0;
for (int s = std::bit_width(c) - 1; s >= 0; s--) {
ll e = d;
d = c >> s;
a = (a << (d - e - 1)) + (n >> (2 * c - e - d + 1)) / a;
}
return a - (a * a > n);
}
#if __has_include(<atcoder/all>) || USE_ACLIBRARY
template <class mint, atcoder::internal::is_static_modint_t<mint>* = nullptr>
std::ostream& operator<<(std::ostream& os, const mint& v) {
return os << v.val();
}
template <class mint, atcoder::internal::is_static_modint_t<mint>* = nullptr>
std::istream& operator>>(std::istream& is, mint& v) {
int tmp;
is >> tmp;
v = tmp;
return is;
}
#endif
template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
return is >> p.first >> p.second;
}
template <class... T>
std::istream& operator>>(std::istream& is, std::tuple<T...>& tpl) {
std::apply([&](auto&&... args) { (is >> ... >> args); }, tpl);
return is;
}
template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (T& x : v) is >> x;
return is;
}
template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (size_t i = 0; i < v.size(); i++)
os << v[i] << (i == v.size() - 1 ? "" : " ");
return os;
}
template <class I, class T>
std::vector<T> make_vector(I n, const T& x) {
return std::vector<T>(n, x);
}
template <class I, class J, class K, class... Ts>
auto make_vector(I i, J j, K k, Ts&&... xs) {
return std::vector(i, make_vector(j, k, xs...));
}
struct Initialization {
Initialization() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
} initialization;
constexpr const std::pair<int, int> DIRS[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
template <typename T>
using infs = std::numeric_limits<T>;
template <typename T>
class factorials {
public:
static size_t n;
static std::vector<T> fact, inv_fact;
static inline void extend(size_t m) {
if (m <= n) return;
fact.resize(m + 1);
inv_fact.resize(m + 1);
for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i;
inv_fact[m] = fact[m].inv();
for (size_t i = m; i > n + 1; i--) inv_fact[i - 1] = inv_fact[i] * i;
n = m;
}
static T inv(int k) {
extend(k);
return inv_fact[k];
}
static T get(int k) {
extend(k);
return fact[k];
}
static T perm(int n, int k) {
if (n < k) return 0;
if (k < 0) return 0;
extend(n);
return fact[n] * inv_fact[n - k];
}
static T choose(int n, int k) {
if (n < k) return 0;
if (k < 0) return 0;
extend(n);
return fact[n] * inv_fact[n - k] * inv_fact[k];
}
static T catalan(int n) { return get(2 * n) * inv(n + 1) * inv(n); }
};
template <typename T>
size_t factorials<T>::n = 0;
template <typename T>
std::vector<T> factorials<T>::fact = {1};
template <typename T>
std::vector<T> factorials<T>::inv_fact = {1};
#if __has_include(<atcoder/all>) || USE_ACLIBRARY
using mint = atcoder::modint998244353;
// using mint = atcoder::modint1000000007;
using fs = factorials<mint>;
#endif
template <typename T>
using pq_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;
namespace pbds = __gnu_pbds;
template <typename T>
using tree = pbds::tree<T, pbds::null_type, std::less<T>, pbds::rb_tree_tag,
pbds::tree_order_statistics_node_update>;
struct node {
using pointer = std::shared_ptr<node>;
bool val;
pointer next;
static pointer mk(bool val, pointer next) {
return std::make_shared<node>(val, next);
}
};
int main() {
ll N;
std::cin >> N;
if (N == 2) {
std::println("! -1");
return 0;
}
auto ask = [](int a, int b) -> int {
if (a > b) {
std::swap(a, b);
}
std::cout << std::format("? {} {}", a, b) << std::endl;
;
int p;
std::cin >> p;
return p;
};
std::vector<int> ans(N, -1);
std::vector<pii> tmp;
rep(i, 1, N) {
int ab = ask(N - 1, N - i - 1);
if (ab == 0) {
ans[i] = 0;
} else {
tmp.emplace_back(i, ab);
}
}
if (tmp.size() < 2) {
int k = tmp.size() ? isqrt(tmp[0].second) : 0;
if (tmp.size() and k * k == tmp[0].second) {
ans[0] = ans[tmp[0].first] = k;
} else {
std::println("! -1");
return 0;
}
} else {
auto [b, ab] = tmp[0];
auto [c, ac] = tmp[1];
int bc = ask(N - b - 1, N - c - 1);
int g = std::gcd(ab, ac);
int k2 = bc / (ab * ac / (g * g));
int k = isqrt(k2);
assert(k * k == k2);
int a = g / k;
ans[0] = a;
for (auto [i, x] : tmp) {
ans[i] = x / a;
}
}
std::print("! ");
for (auto d : ans) {
std::print("{}", d);
}
std::println();
}