#include #include #include #include #include #include #include #include #include #include // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // #include "Src/DataStructure/Heap/BinaryHeap.hpp" // #include "Src/Number/LinearSieve.hpp" namespace zawa {} using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0 ; i < ssize(v) ; i++) os << v[i] << (i + 1 == ssize(v) ? "" : " "); return os; } /* * n桁に対してn回クエリがある * S[1]は正だから、S[2],...,S[N]をS[1]と一緒に聞くと、全部S[1]の倍数になる (ついでに0の桁がわかる) * 0がN-1桁あるとダメ * 0がN-2桁で非零を聞いたときに1より大きいとダメ * それ以外はなんとかなっている? * それ以外は非零の二けたで最後の一回を聞くことで、先頭桁が特定できて、全部特定できる * WA: まじ? * WA: 42ケース * X = 110は特定できる? * WA: 36ケース * REにならない -> cntは1になっている。そこのパートで特定できているならXは特定できているので、そこに入らない値にミスがある * これ降順だ... * WA: 11ケース。まだ違うの? * -1であるものに回答しているか、回答できるものに-1を返している * 99とか? */ int N; #ifdef DEBUG int ANS; int query(int a,int b) { a = N - a - 1; b = N - b - 1; if (a > b) swap(a,b); assert(0 <= a and a < b and b <= N - 1); auto s = to_string(ANS); return (s[N-a-1]-'0')*(s[N-b-1]-'0'); } #else int query(int a,int b) { a = N - a - 1; b = N - b - 1; if (a > b) swap(a,b); cout << "? " << a << ' ' << b << endl; cin >> a; if (a == -1) exit(0); return a; } #endif string solve() { vector dat(N), pos; int g = 0; for (int i = 1 ; i < N ; i++) { dat[i] = query(0,i); if (dat[i] == -1) exit(0); if (dat[i] > 0) pos.push_back(i); g = gcd(g,dat[i]); } vector>> counts(100); for (int i = 0 ; i <= 9 ; i++) for (int j = 0 ; j <= 9 ; j++) counts[i*j].push_back({i,j}); for (int i = 0 ; i < 100 ; i++) if (ssize(counts[i]) == 1 and ranges::find(dat,i) != dat.end()) { vector ans(N); ans[0] = counts[i][0].first; for (int i = 1 ; i < N ; i++) ans[i] = dat[i]/ans[0]; string res; for (int i = 0 ; i < N ; i++) res += ans[i] + '0'; return res; } if (g == 0) return "-1"; else if (ssize(pos) < 2) return "-1"; int v = query(pos[0],pos[1]); int cnt = 0; vector ans(N); for (int i = 1 ; i <= g ; i++) if (g % i == 0 and dat[pos[0]]/i*dat[pos[1]]/i == v) { cnt++; ans[0] = i; } assert(cnt == 1); for (int i = 1 ; i < N ; i++) ans[i] = dat[i]/ans[0]; string res; for (int i = 0 ; i < N ; i++) res += '0' + ans[i]; return res; } int main() { // cin.tie(0); // cout.tie(0); // ios::sync_with_stdio(0); // cout << fixed << setprecision(20); #if !defined DEBUG cin >> N; string ans = solve(); cout << "! " << ans << endl; #else mt19937_64 mt{random_device{}()}; for (int testcase = 0 ; ; ) { cerr << "----------" << ++testcase << "----------" << endl; ANS = (mt() % (int)1e3 + 10); N = to_string(ANS).size(); auto a = solve(); if (a != "-1" and a != to_string(ANS)) { cerr << ANS << "fail" << endl; exit(0); } // auto a = solve(), b = naive(); // if (a != b) { // // print testcase // cerr << "you: " << a << endl; // cout << "correct: " << b << endl; // exit(0); // } } #endif }