BOJ 28270 - Marked-Numbered

BOJ 28270 - Marked-Numbered

스택을 이용한 구현 문제이다.

자신보다 높이가 $1$ 낮은 부모가 아직 나오지 않았다면 정답은 불가능하다.

그렇지 않다면 스택에서 자신보다 높이가 더 큰것을 모두 뺀다.

빼면서 그 높이에 있는 것들의 인덱스를 그 높이에 해당하는 인덱스에 있는 것들끼리 $1$부터 메겨준다.

const int MAX = 1e6;
void solve() {
   int n;
   cin >> n;
   vi lv(n);
   fv(lv);
   vvi by_level(MAX + 5);
   vi ans(n), last(MAX + 1, -1);
   last[0] = 0;
   by_level[0].pb(0);

   vi st;

   for (int i = 0; i < n; i++) {
      if (sz(by_level[lv[i] - 1]) == 0) {
         cout << -1;
         return;
      }
      while (sz(st) && st.back() > lv[i]) {
         if (~last[st.back()]) {
            auto &list = by_level[st.back()];
            for (int j = 0; j < sz(list); j++) {
               ans[list[j]] = j + 1;
            }
            last[st.back()] = -1;
            list.clear();
         }
         st.pop_back();
      }

      st.push_back(lv[i]);
      by_level[lv[i]].pb(i);
      last[lv[i]] = i;
   }
   while (sz(st)) {
      if (~last[st.back()]) {
         auto &list = by_level[st.back()];
         for (int j = 0; j < sz(list); j++) {
            ans[list[j]] = j + 1;
         }
         last[st.back()] = -1;
         list.clear();
      }
      st.pop_back();
   }
   for (int i: ans) cout << i << ' ';
}