There are N numbers in a sequence. The original sequence is from 1 to N. (1 is the head).
For example, if N=5, the original sequence should be 1 2 3 4 5.
There are three commands in the input as follows:
The operation “Move1 a” means to move the first two numbers to the BACK of a without changing order.
For example, if the original sequence is 5 1 4 3 2 , "Move1 4" will turn the sequence into 4 5 1 3 2.
Note that if a is one of the first two numbers then you don't need to do anything.
The operation “Move2 a” means to move the first two numbers to the BACK of a with reversed order.
For example, if the original sequence is 5 1 4 3 2, "Move2 3" will turn the sequence into 4 3 1 5 2.
Note that if a is one of the first two numbers then you don't need to do anything.
The operation “Reverse” means to reverse the whole sequence.
For example, if the original sequence is 5 1 4 3 2, "Reverse" will turn the sequence into 2 3 4 1 5.
Given several such commands and output the final status of the sequence.
You can use the following code.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _node{
int n;
struct _node* prev;
struct _node* next;
}node;
int main(){
int N,M;
char cmd[10];
scanf("%d%d",&N,&M);
// initialize your structures here
for(int i=0;i<M;i++){
scanf("%s",cmd);
if(strcmp(cmd,"Reverse")==0){
//your code here
}else if(strcmp(cmd,"Move1")==0){
//your code here
}else if(strcmp(cmd,"Move2")==0){
//your code here
}
}
//output
/*
Here is an example of output from class but you have to modify it according to your algorithm.
while(head!=NULL){
if(head->prev == NULL) printf("%d", head->data);
else printf(" %d", head->data);
head = head->next;
}
printf("\n");
*/
return 0;
}
The input begins with two integers N and M, indicating there are N numbers in the original sequence and there are M commands in this testcase.
The next M lines will be the commands.
subtask 1 : 3<=N<=100, 1<=M<=100, including Move1, you can use O(N) algorithm.
subtask 2 : 3<=N<=100, 1<=M<=100, including Move1, you can use O(N) algorithm.
subtask 3 : 3<=N<=100, 1<=M<=100, including Move1, you can use O(N) algorithm.
subtask 4 : 3<=N<=10000, 1<=M<=1000000, including Move1, you should use O(1) algorithm.
subtask 5 : 3<=N<=10000, 1<=M<=1000000, including Move1 and Move2, you should use O(1) algorithm.
subtask 6 : 3<=N<=100000, 1<=M<=100000, including Move1 and Move2, you should use O(1) algorithm.
subtask 7 : 3<=N<=100000, 1<=M<=100000, including Move1, Move2 and Reverse, you should use O(1) algorithm.
subtask 8 : 3<=N<=1000000, 1<=M<=1000000, including Move1, Move2 and Reverse, you should use O(1) algorithm.
Output the numbers from the first one to the last one, and separate two consecutive numbers by a space. You NEED to print "\n" at the end of the line.