In this quiz, you will perform operations onto an array-like data structure according to the input. The data structure might not necessarily be a C/C++ array, but for simplicity, we call it an "array" in this problem. You may implement the array in any kind of data structure or data type as you wish.
Your array should have two sides, one side is called the "BACK", while the other side is called the "FRONT". We call the front-most element in the "FRONT" side as the first element, while the back-most element in the "BACK" side as the last element. The first and last element refer to the same element if only 1 element is in the array.
Your goal is to read each line of the input, perform the operation indicated by the input, then finally return the first element and the last element. For detailed input and output format, please refer to the following sections.
Note
1. Your program should be written in C++, compiled by one of the compiling standards provided by the NTHUOJ system.
2. You may use C language or functions in this quiz, as long as the libraries included are supported by the NTHUOJ system.
3. You may implement the "array" in any data structures or data type as you wish, as long as it gives correct output and runs efficiently (within time & memory constraints set by TAs).
Hints
1. This is a C++ review quiz to show the elegancy and efficiency of STL libraries, using an STL library correctly will make your life easier.
2. The TAs suggest the use of std::vector. With the help of push_back(), front(), back(), size(), [], you may solve this problem easily.
3. If you are confident about your code, but the test cases won't pass, check the output format. Maybe you've missed a blank space or a newline character.
Each line of input contains two values with the format of "[value1] [value2]". The value1 indicates the action, while value2 indicates the data. The two values are seperated by a blankspace and each line ends with a newline character (\n). For the meaning of value1 and value2, please refer the followings.
value1:
- 0: insert value2 as a new element to the "BACK" of the array
- 1: add the value of the last element to the first element, then add value2 to the first element, finally delete the last element
- 2: add the value of the first element to the last element, then add value2 to the last element
value2:
- The data to be added; the type would be an integer (int)
Notes
1. Assume the input has n lines, 1 <= n <= 10,000,000
2. value2 is guaranteed to fit a 32-bit int
3. At any moment, the values of the elements in the array is guaranteed to fit a 32-bit int
4. The first and last element may refer to the same element
5. At any moment, the array contains at least 0 element
6. The word "insert" represents inserting a new element into array, which changes the size of array
7. The word "delete" represents removing an element from the array, which changes the size of array
8. The word "add" represents mathematical addition of two values, which will not change the size of array
The output should have the format of "[first-element] [last-element]". The two values should be seperated by a blankspace, and ends with a newline character (\n).
The first-element is the element in the "FRONT" of the array after completed all operations required by the input, while the last-element is the element in the "BACK" of the array after completed all operations.