Official
D - Draw Your Cards Editorial by en_translator
This problem can be solved with a data structure that supports the following operations:
- Add / Remove a value \(X\) as an element.
- Find the smallest element greater than a value \(X\).
For example, C++ supports a data structure called set for this purpose.
This time, we will explain an algorithm while maintaining the following information:
\(under_i\) … \(i\) the (face-up) card stacked right under \(i\)
\(pile_i\) … the number of cards in the pile when \(i\) is stacked on the top of the pile
Process the cards in order by the following procedure.
- We will store the face-up topmost cards on the table in the data structure.
- Find the smallest face-up topmost card greater than \(X\) on the table (from the data structure.)
- If there is such a card, do the following.
- Let \(under_X=Y\).
- Let \(pile_X=pile_Y+1\).
- Remove \(Y\) from the data structure and insert \(X\).
- If there is no such card, do the following, which simulates placing Card \(X\) without stacking onto anything:
- Let \(pile_X=1\).
- (You may set anything to \(under_X\).)
- Insert \(X\) to the data structure.
- If \(pile_X=K\), then the pile has \(K\) cards, so eat them as follows:
- First, we are going to eat the pile containing Card \(X\), so remove \(X\) from the data structure.
- Then, eat Card \(X\). Now, Card \(under_X\) shows up face up, so let \(X \leftarrow under_X\). Repeat this until eating \(K\) cards.
- Repeat the steps above until running out of cards in the deck.
Sample code (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;
}
posted:
last update: