結果

問題 No.3592 I Love LIS
コンテスト
ユーザー Taiki0715
提出日時 2026-07-17 22:22:18
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,352 ms / 8,000 ms
+ 20µs
コード長 16,248 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,535 ms
コンパイル使用メモリ 353,376 KB
実行使用メモリ 5,888 KB
平均クエリ数 4633.08
最終ジャッジ日時 2026-07-17 22:22:43
合計ジャッジ時間 24,233 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<type_traits>
//return Index
template<typename T>
std::enable_if_t<std::is_arithmetic_v<T>,std::vector<int>>longest_increasing_subsequence(const std::vector<T>&a){
  if(a.empty())return std::vector<int>();
  static constexpr T inf=std::numeric_limits<T>::max();
  int n=a.size();
  std::vector<T>dp(n,inf);
  std::vector<int>id(n,-1);
  std::vector<int>pre(n);
  for(int i=0;i<n;i++){
    int l=-1,r=n-1;
    while(r-l>1){
      int mid=(l+r)/2;
      (dp[mid]<a[i]?l:r)=mid;
    }
    if(r)pre[i]=id[r-1];
    dp[r]=a[i];
    id[r]=i;
  }
  int sz=n;
  while(dp[sz-1]==inf)sz--;
  std::vector<int>res(sz);
  res[sz-1]=id[sz-1];
  for(int i=sz-2;i>=0;i--)res[i]=pre[res[i+1]];
  return res;
}
struct has_update_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.update(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_update_v=has_update<T>::value;
struct has_push_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.push(),std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_push_v=has_push<T>::value;
struct has_middle_impl{
  template<typename T>
  static auto check(T&&x)->decltype(x.middle,std::true_type{});
  template<typename T>
  static auto check(...)->std::false_type;
};
template<typename T>
struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_middle_v=has_middle<T>::value;

template<typename T,bool no_push=false>
void splay(T*nd){
  if constexpr(has_push_v<T>&&!no_push)nd->push();
  while(nd->par){
    T *p=nd->par;
    T *pp=p->par;
    if constexpr(has_push_v<T>&&!no_push){
      if(pp)pp->push();
      p->push();
      nd->push();
    }
    if(p->left==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->left=p->right;
          if(pp->left)pp->left->par=pp;
          p->left=nd->right;
          if(p->left)p->left->par=p;
          nd->right=p;
          p->par=nd;
          p->right=pp;
          pp->par=p;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->left=nd->right;
          if(p->left)p->left->par=p;
          pp->right=nd->left;
          if(pp->right)pp->right->par=pp;
          nd->left=pp;
          pp->par=nd;
          nd->right=p;
          p->par=nd;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->left=nd->right;
      if(p->left)p->left->par=p;
      nd->right=p;
      p->par=nd;
      if constexpr(has_update_v<T>)p->update(),nd->update();
      break;
    }
    else if(p->right==nd){
      if(pp){
        if(pp->left==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          p->right=nd->left;
          if(p->right)p->right->par=p;
          pp->left=nd->right;
          if(pp->left)pp->left->par=pp;
          nd->left=p;
          p->par=nd;
          nd->right=pp;
          pp->par=nd;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
        else if(pp->right==p){
          nd->par=pp->par;
          if(pp->par){
            if constexpr(has_middle_v<T>){
              if(pp->par->middle==pp)nd->par->middle=nd;
              else if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
            else{
              if(pp->par->left==pp)nd->par->left=nd;
              else if(pp->par->right==pp)nd->par->right=nd;
            }
          }
          pp->right=p->left;
          if(pp->right)pp->right->par=pp;
          p->right=nd->left;
          if(p->right)p->right->par=p;
          nd->left=p;
          p->par=nd;
          p->left=pp;
          pp->par=p;
          if constexpr(has_update_v<T>)pp->update(),p->update(),nd->update();
          continue;
        }
      }
      nd->par=pp;
      if(pp){
        if constexpr(has_middle_v<T>){
          if(pp->middle==p)pp->middle=nd;
          else if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
        else{
          if(pp->left==p)pp->left=nd;
          else if(pp->right==p)pp->right=nd;
        }
      }
      p->right=nd->left;
      if(p->right)p->right->par=p;
      nd->left=p;
      p->par=nd;
      if constexpr(has_update_v<T>)p->update(),nd->update();
      break;
    }
    else break;
  }
}
template<typename T>
[[nodiscard]]T* near(T *nd,decltype(T::key)k){
  while(true){
    if(k<nd->key){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->left)nd=nd->left;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else if(nd->key<k){
      if constexpr(has_push_v<T>)nd->push();
      if(nd->right)nd=nd->right;
      else{
        splay<T,true>(nd);
        return nd;
      }
    }
    else{
      splay<T,true>(nd);
      return nd;
    }
  }
  return nullptr;
}
template<typename T>
[[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){
  while(true){
    if constexpr(has_push_v<T>)nd->push();
    decltype(T::sz) lsz=nd->left?nd->left->sz:0;
    if(lsz==k)break;
    else if(k<lsz)nd=nd->left;
    else{
      nd=nd->right;
      k-=1+lsz;
    }
  }
  splay<T,true>(nd);
  return nd;
}
template<typename T>
[[nodiscard]]T* merge(T* l,T *r){
  if(!l)return r;
  if(!r)return l;
  while(r->left){
    if constexpr(has_push_v<T>)r->push();
    r=r->left;
  }
  if constexpr(has_push_v<T>)r->push();
  splay<T,true>(r);
  r->left=l;
  l->par=r;
  if constexpr(has_update_v<T>)r->update();
  return r;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* left_most(T*nd){
  T nil;
  T *rnd=&nil;
  while(nd->left){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->left;
    if(!c->left){
      rnd->left=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=rnd;
      rnd=rnd->left;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->left=c->right;
      c->right=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->left)nd->left->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>)nd->update();
      if constexpr(has_update_v<T>||correct_parent)c->par=rnd;
      rnd->left=c;
      nd=c->left;
      rnd=rnd->left;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  rnd->left=nd->right;
  nd->right=nil.left;
  nil.left=nil.right=nullptr;
  if constexpr(has_update_v<T>||correct_parent){
    if(rnd->left)rnd->left->par=rnd;
    if(nd->right)nd->right->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(rnd!=&nil){
      while(rnd){
        rnd->update();
        rnd=rnd->par;
      }
    }
  }
  return nd;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* right_most(T*nd){
  T nil;
  T *lnd=&nil;
  while(nd->right){
    if constexpr(has_push_v<T>)nd->push();
    T *c=nd->right;
    if(!c->right){
      lnd->right=nd;
      if constexpr(has_update_v<T>||correct_parent)nd->par=lnd;
      lnd=lnd->right;
      nd=c;
    }
    else{
      if constexpr(has_push_v<T>)c->push();
      nd->right=c->left;
      c->left=nd;
      if constexpr(has_update_v<T>||correct_parent){
        if(nd->right)nd->right->par=nd;
        nd->par=c;
      }
      if constexpr(has_update_v<T>){
        nd->update();
      }
      if constexpr(has_update_v<T>||correct_parent)c->par=lnd;
      lnd->right=c;
      nd=c->right;
      lnd=lnd->right;
    }
  }
  if constexpr(has_push_v<T>)nd->push();
  lnd->right=nd->left;
  nd->left=nil.right;
  nil.left=nil.right=nullptr;
  if constexpr(has_update_v<T>||correct_parent){
    if(lnd->right)lnd->right->par=lnd;
    if(nd->left)nd->left->par=nd;
    nd->par=nullptr;
  }
  if constexpr(has_update_v<T>){
    if(lnd!=&nil){
      while(lnd){
        lnd->update();
        lnd=lnd->par;
      }
    }
  }
  return nd;
}
template<typename Compare>
std::vector<int>merge_insertion_sort(int n,const Compare&compare){
  struct node{
    node *left=nullptr,*right=nullptr,*par=nullptr;
    int key=-1;
    int sz=1;
    inline void update(){
      sz=1;
      if(left)sz+=left->sz;
      if(right)sz+=right->sz;
    }
  };
  auto dfs=[&](auto self,std::vector<int>&idx)->void {
    int m=idx.size();
    if(m==1)return;
    int amari=-1;
    if(m&1){
      amari=idx.back();
      m--;
    }
    std::vector<std::pair<int,int>>small;
    std::vector<int>large;
    small.reserve(m/2);
    large.reserve(m/2);
    for(int i=0;i<m;i+=2){
      int a=idx[i],b=idx[i+1];
      if(compare(a,b))small.emplace_back(a,b),large.emplace_back(b);
      else small.emplace_back(b,a),large.emplace_back(a);
    }
    self(self,large);
    std::vector<int>pos(n,-1);
    for(int i=0;i<m/2;i++)pos[large[i]]=i;
    std::vector<int>small_v(m/2+(amari!=-1));
    for(const auto&[a,b]:small)small_v[pos[b]]=a;
    if(amari!=-1){
      small_v.back()=amari;
      m++;
    }
    std::vector<node>nds;
    nds.reserve(m);
    nds.resize(large.size()+1);
    nds[0].key=small_v[0];
    node *root=&nds[0];
    for(int i=0;i<(int)large.size();i++){
      root->par=&nds[i+1];
      nds[i+1].left=root;
      root=root->par;
      root->key=large[i];
      root->update();
    }
    for(int i=1,j=2,k=4;i<(int)small_v.size();i+=j,j=k-j,k<<=1){
      for(int l=std::min<int>(small_v.size(),i+j)-1;l>=i;l--){
        int left=-1,right=std::min<int>(root->sz,i*2+j-1);
        while(right-left>1){
          int mid=(left+right)/2;
          root=get_k(root,mid);
          if(compare(root->key,small_v[l]))left=mid;
          else right=mid;
        }
        nds.emplace_back();
        node *nd=&nds.back();
        nd->key=small_v[l];
        if(right==root->sz){
          nd->left=root;
          root->par=nd;
          root=nd;
          root->update();
        }
        else{
          root=get_k(root,right);
          nd->left=root->left;
          if(nd->left)nd->left->par=nd;
          nd->update();
          nd->par=root;
          root->left=nd;
          root->update();
        }
      }
    }
    for(int i=0;i<m;i++){
      root=left_most(root);
      idx[i]=root->key;
      if(i+1==m)break;
      node *nd=root->right;
      nd->par=nullptr;
      root->right=nullptr;
      root=nd;
    }
  };
  std::vector<int>res(n);
  std::iota(res.begin(),res.end(),0);
  dfs(dfs,res);
  return res;
}
void SOLVE(){
  int n;
  cin>>n;
  #ifdef LOCAL
  vector<int>p(n);
  cin>>p;
  #endif
  auto query=[&](vector<int>a)->int {
    assert(a.size()==n);
    cout<<"?";
    rep(i,a.size())cout<<' '<<a[i];
    cout<<endl;
    #ifdef LOCAL
    vector<int>s(n);
    rep(i,n)s[i]=a[p[i]];
    return longest_increasing_subsequence(s).size();
    #else
    int res;
    cin>>res;
    return res;
    #endif
  };
  int rv=[&](){
    rep(i,n){
      vector<int>a(n);
      a[i]=-1;
      if(query(a)==1)return i;
    }
    return -1;
  }();
  int lv=[&](){
    rep(i,n){
      vector<int>a(n);
      a[i]=1;
      if(query(a)==1)return i;
    }
    return -1;
  }();
  vector<int>ord;
  rep(i,n)if(i!=lv&&i!=rv)ord.push_back(i);
  auto comp=[&](int lhs,int rhs)->bool {
    vector<int>a(n,100);
    a[rv]=2;
    a[lv]=-1;
    a[lhs]=0;
    a[rhs]=1;
    return query(a)==4;
  };
  if(n-2>0){
    vector<int>ord2=merge_insertion_sort(ord.size(),[&](int lhs,int rhs){
      return comp(ord[lhs],ord[rhs]);
    });
    vector<int>ord3(ord.size());
    rep(i,ord.size())ord3[i]=ord[ord2[i]];
    ord=ord3;
  }
  debug(lv,rv);
  vector<int>ans(n);
  ans[0]=lv;
  ans[n-1]=rv;
  rep(i,ord.size())ans[i+1]=ord[i];
  cout<<'!';
  rep(i,n)cout<<' '<<ans[i]+1;
  cout<<endl;
  #ifdef LOCAL
  assert(p==ans);
  #endif
}
0