#include using namespace std; template struct BIT { int n; std::vector tree; BIT(int n) : n(n) { tree.assign(n + 1, T(0)); } BIT() {} T _sum(int i) { i++; T res = T(0); while (i > 0) { res += tree[i]; i -= i & -i; } return res; } T sum(int l, int r) { return _sum(r - 1) - _sum(l - 1); } T sum(int r) { return _sum(r - 1); } T get(int i) { return _sum(i) - _sum(i - 1); } void add(int i, T x) { i++; while (i <= n) { tree[i] += x; i += i & -i; } } int lower_bound(T x) { int pos = 0; int plus = 1; while (plus * 2 <= n) plus *= 2; while (plus > 0) { if ((pos + plus <= n) && (tree[pos + plus] < x)) { x -= tree[pos + plus]; pos += plus; } plus >>= 1; } return pos; } }; struct Factoradic : std::vector { using std::vector::vector; void shrink() { while (this->size() >= 2u && !this->back()) { this->pop_back(); } } Factoradic &operator+=(const Factoradic &rhs) { this->resize(std::max(this->size(), rhs.size()) + 1); for (size_t i = 0; i < rhs.size(); ++i) { (*this)[i] += rhs[i]; } for (size_t i = 0; i + 1 < this->size(); ++i) { if ((*this)[i] >= i + 1) { (*this)[i + 1] += (*this)[i] / (i + 1); (*this)[i] -= (i + 1); } } shrink(); return *this; } Factoradic &operator/=(int rhs) { for (int i = int(this->size()) - 1; i >= 0; --i) { if (i) { (*this)[i - 1] += (*this)[i] % rhs * i; } (*this)[i] /= rhs; } shrink(); return *this; } bool operator==(const Factoradic &rhs) const { for (size_t i = 0; i < std::min(this->size(), rhs.size()); ++i) { if ((*this)[i] != rhs[i]) return false; } if (this->size() > rhs.size()) { for (size_t i = rhs.size(); i < this->size(); ++i) { if ((*this)[i] != 0) return false; } } else { for (size_t i = this->size(); i < rhs.size(); ++i) { if (rhs[i] != 0) return false; } } return true; } Factoradic operator+(const Factoradic &rhs) const { Factoradic ret = *this; ret += rhs; return ret; } Factoradic operator/(int rhs) const { Factoradic ret = *this; ret /= rhs; return ret; } std::vector to_permutation(int digit = -1) const { if (digit == -1) digit = int(this->size()); BIT bit(digit); for (int i = 0; i < digit; ++i) { bit.add(i, 1); } std::vector ret; ret.reserve(digit); for (int i = digit - 1; i >= 0; --i) { int x = (i < this->size() ? (*this)[i] : 0); int p = bit.lower_bound(x + 1); ret.push_back(p); bit.add(p, -1); } return ret; } }; void solve() { int n; cin >> n; Factoradic L(n + 1); Factoradic R(n + 1); R[n] = 1; while (1) { auto mid = (L + R) / 2; if (mid == L) break; auto P = mid.to_permutation(n); cout << "? "; for (size_t i = 0; i < P.size(); ++i) { cout << P[i] + 1; if (i != P.size() - 1) cout << " "; } cout << endl; int res; cin >> res; if (res == 0) { R = mid; } else { L = mid; } } auto P = L.to_permutation(n); cout << "! "; for (size_t i = 0; i < P.size(); ++i) { cout << P[i] + 1; if (i != P.size() - 1) cout << " "; } cout << endl; } int main() { // cin.tie(0)->sync_with_stdio(0); // cout << fixed << setprecision(12); int t; t = 1; // cin >> t; while (t--) solve(); return 0; }