13205 - Happy Ball   

Status  |  Limits Submit

Description

This is a partial judge problem OwO

There are  people in a row. From left to right, they are numbered from 1 to . The happy value of the -th person is . And there is a ball which is carried by the first person in the beginning. Now they want to play a game called "Happy Ball".

In this game they need to execute  operations. There are 3 types of operations:

  1. The person who is carrying the ball need to speak out his/her happy value loudly.
  2. The person who is carrying the ball passes the ball to the person on the left side(or right side). This will last  times. The passing direction(i.e to left or to right) will be given and is fixed in one operation. Stop passing if no one is on the corresponding side of the person who is carrying the ball.
  3. The person who is carrying the ball leave the row. Before leaving, he/she would pass the ball to the person on the right side(or left side if no one is on the right side).

This game looks not funny, right?

Anyway, you need to write a program to simulate this game. For each first-type operation, output the happy value of the person who is carrying the ball. In this problem, there is a special constraint: the number of second-type operations times the number of third-type operations is less than or equal to Q.

Solve this problem with array and/or linked list(maintaining the people in the row and who is carrying the ball)!

Hint

The following table is the Time Complexity of each type operation of array and linked list.

 

the first-type

the second-type

the third-type

array

linked list

It's obvious that array is good at the second-type operation and linked list is good at the third-type operation.

So you could depend on the operations to choose the one which is much better and create it.  

Note

In the following code, nullptr is just like NULL in C. You could treat them as the same.

But nullptr is only available in C++11 and beyond. So compiling/submitting your code in C++11 or beyond.

Partial Code

main.cpp

#include <iostream>
#include "function.h"
using namespace std;
int main() {
    /* I/O optimization */
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int *arr = new int[n + 1];
        for(int i=1;i<=n;i++)    cin >> arr[i];

        int q;
        cin >> q;
        Operation *ops = new Operation[q + 1];
        for(int i=1;i<=q;i++) {
            cin >> ops[i].type;
            if(ops[i].type == 2)    cin >> ops[i].d;
        }

        ContainerBase *solver = create(n, arr, q, ops);
        for(int i=1;i<=q;i++) {
            if(ops[i].type == 1)
                cout << solver->print() << '\n';
            else if(ops[i].type == 2)
                solver->move(ops[i].d);
            else
                solver->remove();
        }

        delete[] arr;
        delete[] ops;
        delete solver;
    }
    return 0;
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

/* an abstract class for the container used in this problem */
class ContainerBase {
    public:
        /* for the first-type operation */
        virtual int print() = 0;
        /* for the second-type operation */
        virtual void move(int) = 0;
        /* for the third-type operation */
        virtual void remove() = 0;
        int getSize() { return size; }

        virtual ~ContainerBase() {}
    protected:
        int size;    // the number of elements(people) in the container
};

/* array class deriving from ContainerBase */
class Array final : public ContainerBase {
    public:
        Array() {}
        Array(int n, int *arr) {
            size = n;

            mem = new int[size + 1];
            for(int i=1;i<=size;i++)    mem[i] = arr[i];
            cur = 1;
        }

        virtual int print() override { return mem[cur]; }
        /* TODO */
        virtual void move(int) override;
        /* TODO */
        virtual void remove() override;

        ~Array() { delete[] mem; }
    private:
        int *mem;    // array for maintaining all the elements(the happy value of all the people)
        int cur;    // record who is carrying the ball
};

/* doubly linked list class deriving from ContainerBase */
class List final : public ContainerBase {
    public:
        List() {}
        List(int n, int *arr) {
            size = n;

            cur = new Node(arr[1]);
            Node *back = cur;
            for(int i=2;i<=n;i++) {
                Node *newNode = new Node(arr[i]);
                back->insertBack(newNode);
                back = newNode;
            }
        }

        virtual int print() override { return cur->getVal(); }
        /* TODO */
        virtual void move(int) override;
        /* TODO */
        virtual void remove() override;

        ~List() { for(int i=1;i<=size;i++)    cur = cur->remove(); }
    private:
        /* nested class for the node in linked list */
        class Node {
            public:
                Node() {}
                Node(int newVal) : pre(nullptr), nxt(nullptr), val(newVal) {}
                /* insert a new node after the current node */
                void insertBack(Node *newNode) {
                    nxt = newNode;
                    newNode->pre = this;
                }
                /* remove the current node and return the next node(or the previous node if the next node doesn't exist) */
                Node* remove() {
                    Node *ret = (nxt == nullptr ? pre : nxt);
                    if(pre != nullptr)    pre->nxt = nxt;
                    if(nxt != nullptr)    nxt->pre = pre;
                    delete this;
                    return ret;
                }
                Node* getPre() { return pre; }
                Node* getNxt() { return nxt; }
                int getVal() { return val; }
            private:
                Node *pre, *nxt;
                int val;
        } *cur;    // record who is carrying the ball
};

/* a class for operation */
class Operation {
    public:
        int type,d;
};

/* TODO: create array/linked list based on operations and return it */
ContainerBase* create(int, int*, int, Operation*);

#endif

You need to implement the five functions: Array::move, Array::remove, List::move, List::remove and create.

Input

The very first line contains an integer  – the number of tasks.

The first line of each task contains an integer  – the number of people in the beginning.

The second line contains  integers  – the happy value of all the people.

The third line contains an integer  – the number of operations excuted.

Then  lines follow. The -th line of each task contains an integer  – the type of the -th operation. If  is equal to 2, then an integer  follows. The passing direction of a second-type operation is right when its  is positive or left otherwise. The number of second-type operations times the number of third-type operations is less than or equal to Q.

 

It's guaranteed that:

  • The 1st testcase must be identical to the Sample below
  • For the first 6 testcases: 

Output

For each task, output one line which represents the happy value of who is carrying ball for every first-type operation.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13205.cpp

Partial Judge Header

13205.h

Tags




Discuss