There is a pile of N books on the table. Two types of operations are performed over this pile:
- a book is added to the top of the pile,
- top K books are rotated. If there are less than K books on the table, the whole pile is rotated.
First operation is denoted as ADD(S) where S is the name of the book, and the second operations is denoted as ROTATE.
The maximum number of books is no more than 40000. All book names are non-empty sequences of no more than 3 capital Latin letters. The names of the books can be non-unique.
- a book is added to the top of the pile,
- top K books are rotated. If there are less than K books on the table, the whole pile is rotated.
First operation is denoted as ADD(S) where S is the name of the book, and the second operations is denoted as ROTATE.
The maximum number of books is no more than 40000. All book names are non-empty sequences of no more than 3 capital Latin letters. The names of the books can be non-unique.
Input
The first line of input file contains 3 integer numbers N, M, K (0 <= N <= 40000; 0 <= M <= 100000; 0 <= K <= 40000). The following N lines are the names of the books in the pile before performing any operations. The book names are given in order from top book to bottom. Each of the following M lines contains the operation description.
Output
Output the sequence of books names in the pile after performing all operations. First line corresponds to the top book.
Sample test(s)
Input
2 3 2
A
B
ADD(C)
ROTATE
ADD(D)
A
B
ADD(C)
ROTATE
ADD(D)
Output
D
A
C
B
A
C
B
题意
一堆书，进行两个操作，一个是再堆上一本书，另一个是把上面k本书的顺序调转。现进行了m次操作，问书堆最后的情况。
分析
两种操作都只与上面k本书有关系，可以使用双端队列来模拟，至于调转操作就是选择堆书的一端不同。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include <queue>
#include <vector>
#include<bitset>
#include<map>
#include<deque>
using namespace std;
typedef long long LL;
const int maxn = 1e5+;
const int mod = +;
typedef pair<int,int> pii;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ms(a,b) memset(a,b,sizeof(a))
const int inf = 0x3f3f3f3f;
#define lson l,m,2*rt
#define rson m+1,r,2*rt+1 int main(){
// freopen("in.txt","r",stdin);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
deque<string>q1;
deque<string>q2;
int dir=;
for(int i=;i<n;i++){
char str[];
scanf("%s",str);
if(q1.size()>=k) q2.push_back(string(str));
else q1.push_back(string(str));
}
for(int i=;i<m;i++){
char str[];
scanf("%s",str);
if(str[]=='A'){
string s="";
int len=strlen(str);
int ok=;
for(int j=;j<len;j++){
if(str[j]=='(') ok=;
else if(str[j]==')') ok=;
else if(ok) s+=str[j];
}
if(dir) q1.push_front(s);
else q1.push_back(s); if(q1.size()>k){
if(dir){
q2.push_front(q1.back());
q1.pop_back();
}else{
q2.push_front(q1.front());
q1.pop_front();
}
}
}else dir = !dir;
}
if(dir){
while(!q1.empty()){
cout<<q1.front()<<endl;
q1.pop_front();
}
}else{
while(!q1.empty()){
cout<<q1.back()<<endl;
q1.pop_back();
}
}
while(!q2.empty()){
cout<<q2.front()<<endl;
q2.pop_front();
}
return ;
}