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

由於實際的code有做其他檢查，因此為了讓各位方便閱讀，請參考簡化版本的function.h與main.cpp（請點連結）

Vectors are sequence containers representing arrays that can change in size.

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.

 

Note:

If the value of size is equal to the value of capacity, and you need to change the value of capacity (reallocate memory) when you push_back a new element. The rule of increasing capacity is: new capacity = max(old capacity + 1, old capacity * 3).

The constructor of vector will not create an array (which means size and capacity is 0).

Input

There are seven kinds of commands:

• pop_back: removes the last element
• push_back: adds an element to the end
• capacity: returns the number of elements that can be held in currently allocated storage
• size: returns the number of elements
• insert: inserts elements (If there is no capacity for new elements, the new capacity is max (old capacity + old capacity / 2, old capacity + count of inserting elements).) (If a vector has two elements, inserting three elements at position two means push back three times.) 
• reserve: reserves storage (Increase the capacity of the container to a value that's equal to new capacity. If new capacity is greater than the current capacity, new storage is allocated, otherwise the method does nothing.)
• resize: changes the number of elements stored (If the value of new size is greater than the value of old size, the value of new elements will be 0. If the value of new size is greater than the value of old capacity, the value of new capacity will be new size.)

Each commands is followed by a new line character ('\n').

Output

Implement Vector (constructor, push_back(), pop_back(), capacity(), size(), reserve(), resize(), insert() and destructor).

Sample Input  Download

Sample Output  Download

Partial Judge Code

11410.cpp

Partial Judge Header

11410.h

Tags

Discuss

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

由於實際的code有做其他檢查，因此為了讓各位方便閱讀，請參考簡化版本的function.h與main.cpp（請點連結）

 

You are required to implement a list.

You have to enable C++11 in this problem. (e.g. "g++ -std=c++11 ...")

Input

The input consist of a number of operations. Each operations (erase, insert and S) are separated by a newline character ('\n').

Operation insert: following by a non-negative integer (insert position) and a non-negative integer (insert value, 0<=insert value<65535). Insert a node at insert position with insert value.

Operation erase: following by a non-negative integer (erase position). Erase a node at erase position.

Operation show: print the value of all nodes in the list. Print a whitespace character (' ') after printing the value of nodes. If the list is empty, do not print anything.

Output

如果不知道operator<<如何實作，可以看 main.cpp

Implement List (constructor, destructor, erase and insert), operator<<(std::ostream &,const List &lst).

Sample Input  Download

Sample Output  Download

Partial Judge Code

11430.cpp

Partial Judge Header

11430.h

Tags

Discuss

Description

You need to implement the following functions for a binary search tree data structure:

  BST(); // constructor, does what needs to be done when created
  ~BST();  // destructor, doest what needs to be done when destroyed
  void insert(int v); // insert a node with value v if v is not in the tree
  void erase(int v); // delete a node with value v if v is in the tree
  string inorder(); // returns a string representing the values in the inorder traversal, separated by a space

There is only one private member "Node *root" in BST. The definition of Node is as follows:

struct Node {
  int val;
  Node *lc; // left child
  Node *rc; // right child
  Node(int v) : val(v), lc(nullptr), rc(nullptr) {} // init to null when created
};

Note that depending on your implementation, the relation between nodes of your BST and those of others' may be different, but it's alright because the inorder will be the same.

 

***UPDATE***

In case you have no idea how to implement `erase`, here's a blueprint for a simple algorithm:

// A recursive function to delete v from subtree cur, where par is parent of cur
void dfs(Node *cur, Node *par, int v) {
  if (cur is empty) return; // obviously...
  if (cur is the node you want to delete) {
    if (cur has both left and right children) {
      Set par->lc or par->rc to cur->lc depending on the relation between par and cur;
      (the node with the largest value in subtree rooted at cur->lc)->rc = cur->rc;
    } else {
      If you know what's happening so far, you should know what goes here
    }
    remove cur from existence;
    dfs to either cur->lc or cur->rc depending on whether v < cur->val is true;
}

In case you do spot a possible corner case in this implementation, you may consider taking care of it on your own, or having an extra node for infinity in the beginning (if you see how this helps).

Input

Q
OP_1
OP_2
...
OP_Q

Where Q is an integer representing the number of operations. Q lines follow.
OP_i is the i'th operation, and it may be one of the three following forms:

0 V
1 V
2

Where "0 V" will need you to insert V into the BST (if V exists already, you should ignore this), "1 V" needs you to delete V in the BST (if V does not exist, ignore this), and "2" needs you to print the inorder traversal. The operations has to be accomplished in the order they are given.

1 <= Q <= 2000
0 <= V <= 10^9

Output

For each operation "2", print the inorder traversal in a line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12721.cpp

Partial Judge Header

12721.h

Tags

Discuss