\(X_i = 0\) である場合への対処を工夫します。

• 箱 \(1\) の \(1\) 個目
• 箱 \(2\) の \(1\) 個目
• \(\vdots\)
• 箱 \(N\) の \(1\) 個目
• 箱 \(1\) の \(2\) 個目
• 箱 \(2\) の \(2\) 個目
• \(\vdots\)
• 箱 \(N\) の \(2\) 個目
• 箱 \(1\) の \(3\) 個目
• \(\vdots\)

というように着目した場合、 \(X_i=0\) の際のボールの処遇は上記の列のうち先頭 \(Q\) 項目までしか発生しません。
なぜなら、これらのうちより前にある項をそっちのけにして \(X_i=0\) のボールを入れた時、その行為はボールの入れ方のルールに違反していることが分かるからです。
逆に、先ほどの列を上から順に調べることで、 \(X_i=0\) なるボールの処遇を調べることができます。

これを利用した下記の実装は時間計算量 \(O(N+Q)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> bk(N+1,0);
  int p=1,q=1;
  for(int i=0;i<Q;i++){
    if(i){cout << " ";}

    int X;
    cin >> X;
    if(X>=1){
      bk[X]++;
      cout << X;
    }
    else{
      while(bk[p]>=q){
        p++;
        if(p==N+1){
          p=1; q++;
        }
      }
      bk[p]++;
      cout << p;
    }
  }
  cout << "\n";
  return 0;
}