この問題では、以下の操作ができるデータ構造を使うと解くことができます。

• 要素として値 \(X\) を追加 / 削除する。
• 値 \(X\) より大きい要素であって、最小のものを見つける。

例えば、 C++ では set というデータ構造を使うことができます。

今回は、以下の情報を保持しながらカードを処理していく方針を示します。
\(under_i\) … \(i\) の直下に(表向きに)置かれたカード
\(pile_i\) … \(i\) が下から何枚目に積まれたか (= \(i\) が表向きで見えている時、その山にはカードが何枚積まれているか)

以下の手順でカードを順に処理していけばよいです。

• データ構造には、表向きで場に見えているカードの情報を格納するものとする。
• 場の中(データ構造)から、表向きに見えている \(X\) より大きいカードであって最小のものを探す。
• そのようなカードがあれば(このカードを \(Y\) とする)、以下の操作を行う。
  • \(under_X=Y\) とする。
  • \(pile_X=pile_Y+1\) とする。
  • データ構造から \(Y\) を削除し、 \(X\) を追加する。
• そのようなカードがなければ、カード \(X\) を何にも重ねずに出すため、以下の操作を行う。
  • \(pile_X=1\) とする。
  • ( \(under_X\) は何にしていてもよい。)
  • データ構造に \(X\) を追加する。
• もし \(pile_X=K\) であれば、その山にはカードが \(K\) 枚積み上げられていることになるため、その山を食べることになる。以下の手順で食べれば良い。
  • まず、カード \(X\) を含んだ山は今から食べるので、データ構造から \(X\) を削除する。
  • その後、カード \(X\) を食べる。すると、カード \(under_X\) が表向きになって出てくるので、 \(X \leftarrow under_X\) としてカードを \(K\) 枚食べるまで繰り返す。
• 以上の手順を、山札が無くなるまで繰り返す。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> under(n+5,-1);
  vector<int> pile(n+5,0);
  set<int> st;
  vector<int> res(n+5,-1);
  for(int i=1;i<=n;i++){
    int p;
    cin >> p;
    auto it=st.upper_bound(p);
    if(it==st.end()){
      pile[p]=1;
      st.insert(p);
    }
    else{
      under[p]=(*it);
      pile[p]=pile[(*it)]+1;
      st.erase(it);
      st.insert(p);
    }
    
    if(pile[p]==k){
      st.erase(p);
      int x=p;
      for(int j=0;j<k;j++){
        res[x]=i;
        x=under[x];
      }
    }
  }

  for(int i=1;i<=n;i++){cout << res[i] << "\n";}
  return 0;
}