Description

Warning: You are not allowed to use:

1. any static variables

2. any variables which is not inside a function

3. malloc and free

You are required to implement a iterator.

Random_iter is a array-like pointer which goes next or previous element by increasing or decreasing one memory address.

Bidirect_iter is a linked list-like pointer which goes next or previous element by the next or prev data member of Node.

(After you learning template, you will know how iterator exactly work.)

Input

The first line contains a non-negative integer N (0<N<100) that specifies the number of elements.

The second line contains 2*N integer that specifies the next position of elements and the value ([-32767,32768)) of the next element.

For example, 4 24713 2 21367 5 -3338 1 1893 3 -4723 0 -16458 means

node 0: value is -16458, next is node 4

node 1: value is 1893, next is node 2

node 2: value is 21367, next is node 5

node 3: value is -4723, next is node 1

...

The thrid line contains a non-negative integer H (H<N) that specifies which element is head.

The following lines contain an instruction I (0<=I<4). The meaning of I is shown below:

0 means distance. Containg a non-negative P (P<N, from input) that specifies the distance from head. You have to display the distance between current position and P.

1 means set value. Replace the value of current position with input integer.

2 means next. Set the current position to next.

3 means prev. Set the current position to previous.

Current position is initialized with 0, which points to head.

Output

Complete Node (constructor), Iter (constructor), Random_iter (distance_, next_, prev_ and constructor) and Bidirect_iter (distance_, next_, prev_ and constructor).

Sample Input  Download

Sample Output  Download

Partial Judge Code

11423.cpp

Partial Judge Header

11423.h

Tags

Discuss

Description

You should now be familiar with the implementation of list.

Now we would like you to make your implementation conform to our standards, and that includes supporting iterators.

If you are not familiar with iterators, you might want to have a look at this introductory post.

Please read the .h source file and complete the definitions. You need to define the following functions:

  iterator_impl_base &operator++(); // increments the iterator; the iterator should then point to the next node
  bool operator!=(const iterator_impl_base &) const; // compares whether two iterators point to the same node

  list();
  ~list();
  void clear(); // make this list empty as if it's new
  size_type size() const; // returns the number of elements in the list
  bool empty() const; // returns whether the list is empty
  iterator begin(); // returns an iterator that points to the first node (if none, point to end)
  iterator end(); // returns an iterator that points to a special node that is the node after the last element
  void insert(iterator pos, size_type count, const value_type val); // inserts #count val right before pos
  void erase(iterator l, iterator r); // erase nodes with index in [l, r)

Some tips:
1. In case you need to find the address of Node when you only have the address of a member in Node: post.
2. Stuck with compling issues regarding polymorphism?: post.
3. Don't be scared. The solution by the author has less than 40 lines.

Input

T
N_1
Q_1
Q_2
...
Q_N_1
N_2
...
N_T
...

Q is one of the two types:
"1 X C V"
"2 L R"
Where the former means you'll do insert(X, C, V), and the latter would need you to do erase(L, R).

1 <= T <= 500
1 <= N <= 1000
0 <= C <= 5
0 <= V <= 1000
0 <= L <= R <= The size of the list at the moment
0 <= X <= The size of the list at the moment

 

Output

For each test case (enumerated from 1 to T), print the size of the list in one line, followed by the elements of the list.

Particularly, ignore the test case if the resulting list is empty.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12727.cpp

Partial Judge Header

12727.h

Tags

Discuss

Description

Please do problem 12727 first.

This time, it's about BST. Also, you'll need to define some of the functions in iterator. It would probably help if you read the partial judge source code from 12727 again.

You should know what to do by reading the .h file. However, the following are the specs:

  void insert(const value_type &val); // insert val in tree if val not exist
  iterator lower_bound(const value_type &val); // return iterator to the node whose value is the least among those greater than or equal to val (if none, return end())

 

Edited 5/16: lower_bound: those greater than *or equal to* val

Input

T
N_1
Q_1 Q_2 ... Q_N_1
N_2
Q_1 Q_2 ... Q_N_2
...
N_T
Q_1 Q_2 ... Q_N_T

1 <= T <= 500
1 <= N <= 500
1 <= Q <= 500

T is the number of test cases.
N_i is the number of queries in the i'th test case.
For each Q, you are asked to print the least value greater than or equal to Q in the tree (if none do nothing), and insert Q into the tree.

Output

For each Q, print the least value greater than or equal to Q in one line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12728.cpp

Partial Judge Header

12728.h

Tags

Discuss