#1171859 (C++23) No.3590 I Love Inversions

• 問題: No.3590 I Love Inversions
• ユーザー: edon8618
• 提出日時: 2026-07-17 22:34:30
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 2,151 ms / 5,000 ms
• コード長: 14,117 bytes
• コンパイル時間: 4,682 ms
• コンパイル使用メモリ: 381,592 KB
• 実行使用メモリ: 6,784 KB
• 平均クエリ数: 12103.46
• 最終ジャッジ日時: 2026-07-17 22:35:03
• 合計ジャッジ時間: 27,499 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 43

ソースコード

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;



// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define ll long long
#define ld long double
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

template<class T, class U>
inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T, class U>
inline bool chmin(T &a, const U &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}


// #define ll int
// #define ll int128_t
// #define ll int256_t
// #define ll cpp_int


constexpr ll inf = (1ll << 62);
// constexpr ll inf = (1 << 30);
// const double PI=3.1415926535897932384626433832795028841971;

// uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123;
// inline uint32_t xor_next() {
//     uint32_t t = xor_x ^ (xor_x << 11);
//     xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
//     return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8));
// }
// inline int rnd(int max_val) { return xor_next() % max_val; }


struct Timer {
    std::chrono::steady_clock::time_point start_time;

    Timer() {
        reset();
    }

    // 測定の起点リセット用
    void reset() {
        start_time = std::chrono::steady_clock::now();
    }

    // スタートからの経過時間をミリ秒(msec)で返す
    long long get_ms() const {
        auto now = std::chrono::steady_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time).count();
    }
};

// ll rui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a*rui(a*a,b/2);
//     return rui(a*a,b/2);
// }

// vl fact;
// ll kai(ll n){
//     fact.resize(n,1);
//     rep(i,n-1)fact[i+1]=fact[i]*(i+1);
// }

// using mint = ld;
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = static_modint<922267487>;   // 多分落とされにくい NOT ntt-friendly
// using mint = static_modint<469762049>;   // ntt-friendly
// using mint = static_modint<167772161>;   // ntt-friendly
// using mint = modint;//mint::set_mod(mod);

// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
//     a%=mod;
//     if(b==0)return 1;
//     if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
//     return modrui(a*a%mod,b/2,mod)%mod;
// }

// void incr(vl &v,ll n){//　n進法
//     ll k=v.size();
//     v[k-1]++;
//     ll now=k-1;
//     while (v[now]>=n)
//     {
//         v[now]=0;
//         if(now==0)break;
//         v[now-1]++;
//         now--;
//     }
//     return;
// }

// vector<mint> fact,invf;
// void init_modfact(ll sz){
//     fact.resize(sz);
//     invf.resize(sz);
//     fact[0]=1;
//     rep(i,sz-1){
//         fact[i+1]=fact[i]*(i+1);
//     }
//     invf[sz-1]=1/fact[sz-1];
//     for(ll i=sz-2; i>=0; i--){
//         invf[i]=invf[i+1]*(i+1);
//     }
// }
// mint choose(ll n,ll r){
//     if(n<r || r<0 || n<0)return 0;
//     return fact[n]*invf[r]*invf[n-r];
// }

// vector<mint> modpow,invpow;
// void init_modpow(ll x,ll sz){
//     mint inv=1/mint(x);
//     modpow.assign(sz,1);
//     invpow.assign(sz,1);
//     rep(i,sz-1){
//         modpow[i+1]=modpow[i]*x;
//         invpow[i+1]=invpow[i]*inv;
//     }
// }
// long long phi(long long n) {// O(sqrt(n))
//     long long res = n;
//     for (long long i = 2; i * i <= n; i++) {
//         if (n % i == 0) {
//             res -= res / i;
//             while (n % i == 0) n /= i;
//         }
//     }
//     if (n > 1) res -= res / n;
//     return res;
// }













// https://atcoder.jp/contests/abc314/submissions/73171689
// シンプルなテンプレート AVL 木（multiset 互換の最小実装）
// - T: キーの型
// - Comp: 比較関数（デフォルト less<T>）これで中身は昇順に並ぶ
// 提供する主なメソッド:
//  insert(const T& key) -> int (挿入位置の index)
//  erase(const T& key)  -> int (削除した index、存在しなければ -1)
//  erase_all(const T& key) -> int (削除した個数)
//  contains(const T& key) -> bool
//  lower_bound(const T& key) -> Iterator (最小の >= key の index)
//  upper_bound(const T& key) -> Iterator (最小の >  key の index)
//  at(int k) -> optional<T> (0-indexed k-th 要素)
//  rank(const T& key) -> number of elements < key
//  size(), empty(), to_vector()
template <typename T, typename Comp = std::less<T>>
struct AVLtree {
    struct Node {
        T key;
        Node *l = nullptr, *r = nullptr, *p = nullptr;
        int height = 1;
        int sz = 1;
        Node(const T& k): key(k) {}
    };

    Node* root = nullptr;
    Comp comp;

    AVLtree() = default;
    ~AVLtree(){ clear(); }

    void clear(){ destroy(root); root = nullptr; }

    int size() const { return root ? root->sz : 0; }
    bool empty() const { return root == nullptr; }

    // --- utilities ---
    static int height(Node* x){ return x ? x->height : 0; }
    static int sz(Node* x){ return x ? x->sz : 0; }
    static void update(Node* x){
        if(!x) return;
        x->height = 1 + max(height(x->l), height(x->r));
        x->sz = 1 + sz(x->l) + sz(x->r);
        if(x->l) x->l->p = x;
        if(x->r) x->r->p = x;
    }
    static int bf(Node* x){ return x ? height(x->l) - height(x->r) : 0; }

    Node* rotate_right(Node* y){
        Node* x = y->l;
        Node* b = x->r;
        x->r = y; y->l = b;
        if(b) b->p = y;
        x->p = y->p; y->p = x;
        update(y); update(x);
        return x;
    }
    Node* rotate_left(Node* x){
        Node* y = x->r;
        Node* b = y->l;
        y->l = x; x->r = b;
        if(b) b->p = x;
        y->p = x->p; x->p = y;
        update(x); update(y);
        return y;
    }

    // rebalance subtree rooted at x, returns new root of this subtree
    Node* rebalance(Node* x){
        update(x);
        int balance = bf(x);
        if(balance > 1){
            if(bf(x->l) < 0) x->l = rotate_left(x->l);
            return rotate_right(x);
        }else if(balance < -1){
            if(bf(x->r) > 0) x->r = rotate_right(x->r);
            return rotate_left(x);
        }
        return x;
    }

    // recursive insert helper, duplicates allowed (insert into right subtree)
    pair<Node*, bool> insert_node(Node* node, const T& key){
        if(!node) return { new Node(key), true };
        if(comp(key, node->key)){
            auto pr = insert_node(node->l, key);
            node->l = pr.first; if(node->l) node->l->p = node;
        }else{
            // duplicates also go to right subtree -> multiset 挙動
            auto pr = insert_node(node->r, key);
            node->r = pr.first; if(node->r) node->r->p = node;
        }
        node = rebalance(node);
        return { node, true };
    }

    // insert: always inserts (returns index)
    int insert(const T& key){
        int idx = rank(key);
        auto pr = insert_node(root, key);
        root = pr.first;
        if(root) root->p = nullptr;
        return idx;
    }

    // find min in subtree
    static Node* find_min(Node* x){ while(x && x->l) x = x->l; return x; }
    static Node* find_max(Node* x){ while(x && x->r) x = x->r; return x; }

    // erase by index (0-indexed), returns new subtree root and whether erased
    pair<Node*, bool> erase_kth(Node* node, int k){
        if(!node) return { nullptr, false };
        int lsz = sz(node->l);
        if(k < lsz){
            auto pr = erase_kth(node->l, k);
            node->l = pr.first; if(node->l) node->l->p = node;
            node = rebalance(node);
            return { node, pr.second };
        }
        if(k > lsz){
            auto pr = erase_kth(node->r, k - lsz - 1);
            node->r = pr.first; if(node->r) node->r->p = node;
            node = rebalance(node);
            return { node, pr.second };
        }
        // k == lsz -> delete this node
        if(!node->l || !node->r){
            Node* tmp = node->l ? node->l : node->r;
            if(tmp) tmp->p = node->p;
            delete node;
            return { tmp, true };
        }
        // two children: replace with successor (min in right subtree)
        Node* succ = find_min(node->r);
        node->key = succ->key;
        auto pr = erase_kth(node->r, 0);
        node->r = pr.first; if(node->r) node->r->p = node;
        node = rebalance(node);
        return { node, true };
    }

    // erase a single occurrence; return erased index, or -1 if not found
    int erase(const T& key){
        int idx = lower_bound(key).index();
        if(idx >= size()) return -1;
        auto o = at(idx);
        if(!o || comp(key, *o) || comp(*o, key)) return -1;
        auto pr = erase_kth(root, idx);
        root = pr.first;
        if(root) root->p = nullptr;
        return pr.second ? idx : -1;
    }

    // erase all occurrences of key, return number removed
    int erase_all(const T& key){
        int cnt = 0;
        while(true){
            int idx = erase(key);
            if(idx == -1) break;
            ++cnt;
        }
        return cnt;
    }

    bool contains(const T& key) const {
        Node* cur = root;
        while(cur){
            if(comp(key, cur->key)) cur = cur->l;
            else if(comp(cur->key, key)) cur = cur->r;
            else return true;
        }
        return false;
    }

    // count occurrences of key
    int count(const T& key) const {
        // number of elements < key  と  < upper_bound の差で求める
        int lo = rank(key);
        optional<T> ub = upper_bound(key);
        int hi = ub ? rank(*ub) : size();
        return hi - lo;
    }

    // k-th (0-indexed). return optional
    optional<T> at(int k) const {
        if(k < 0 || k >= size()) return nullopt;
        Node* cur = root;
        while(cur){
            int lsz = sz(cur->l);
            if(k < lsz) cur = cur->l;
            else if(k == lsz) return cur->key;
            else { k -= lsz + 1; cur = cur->r; }
        }
        return nullopt;
    }

    // number of elements strictly less than key
    int rank(const T& key) const {
        int r = 0;
        Node* cur = root;
        while(cur){
            if(comp(key, cur->key)){
                cur = cur->l;
            }else{
                if(!comp(cur->key, key)) { // cur->key >= key
                    cur = cur->l;
                } else {
                    r += 1 + sz(cur->l);
                    cur = cur->r;
                }
            }
        }
        return r;
    }

    // --- iterator-like interface (index-based iterator) ---
    struct Iterator {
        const AVLtree* tree = nullptr;
        int idx = 0; // 0..size()
        Iterator() = default;
        Iterator(const AVLtree* t, int i): tree(t), idx(i) {}
        T operator*() const {
            auto o = tree->at(idx);
            return *o; // assume valid
        }
        Iterator& operator++(){ ++idx; return *this; } // prefix
        Iterator& operator--(){ --idx; return *this; } // prefix
        Iterator& operator+=(int k){ idx += k; return *this; }
        Iterator& operator-=(int k){ idx -= k; return *this; }
        Iterator operator+(int k) const { return Iterator(tree, idx + k); }
        Iterator operator-(int k) const { return Iterator(tree, idx - k); }
        int index() const { return idx; }
        bool valid() const { return tree && idx >= 0 && idx < tree->size(); }
    };

    // lower_bound: returns iterator to first element >= key (index)
    Iterator lower_bound(const T& key) const {
        int idx = 0;
        Node* cur = root;
        int ans = size();
        while(cur){
            if(!comp(cur->key, key)){ // cur->key >= key
                ans = idx + sz(cur->l);
                cur = cur->l;
            }else{
                idx += 1 + sz(cur->l);
                cur = cur->r;
            }
        }
        return Iterator(this, ans);
    }
    // upper_bound: returns iterator to first element > key (index)
    Iterator upper_bound(const T& key) const {
        int idx = 0;
        Node* cur = root;
        int ans = size();
        while(cur){
            if(comp(key, cur->key)){ // key < cur->key
                ans = idx + sz(cur->l);
                cur = cur->l;
            } else {
                idx += 1 + sz(cur->l);
                cur = cur->r;
            }
        }
        return Iterator(this, ans);
    }

    // inorder to vector
    void inorder(Node* t, vector<T>& out) const {
        if(!t) return;
        inorder(t->l, out);
        out.push_back(t->key);
        inorder(t->r, out);
    }
    vector<T> to_vector() const {
        vector<T> v; v.reserve(size());
        inorder(root, v);
        return v;
    }

private:
    void destroy(Node* t){
        if(!t) return;
        destroy(t->l);
        destroy(t->r);
        delete t;
    }
};

void solve() {
    ll n;
    cin >> n;
    
    vl v(n,0);
    rep(i,n-1){
        cout << "? " << 1 << " " << i+2 << endl;
        cin >> v[i+1];
    }

    for(ll i=n-1;i>0;i--){
        v[i]-=v[i-1];
    }

    AVLtree<ll> st;
    rep(i,n)st.insert(i);
    vl ans(n,-1);
    rep(i,n){
        ans[n-1-i]=*st.at(st.size()-1-v[n-1-i]);
        st.erase(*st.at(st.size()-1-v[n-1-i]));
    }

    cout << "! ";
    rep(i,n)cout << ans[i]+1 << " \n"[i==n-1];
}



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


    // ll mx=450;
    // vc fl(mx+1,0);
    // for(ll d=2;d<=mx;d++){
    //     if(fl[d])continue;
    //     ll x=d;
    //     ps.push_back(x);
    //     while(x<=mx){
    //         fl[x]=1;
    //         x+=d;
    //     }
    // }
    


    ll t = 1;
    // cin >> t;
    while (t--){
        solve();
    }
}