Inserting and deleting elements in a list

In my code, I use fast method of reading input and a custom model of list. After reading the input into my 'list'.

The problem is that, when I test my code, most answers are correct, but for some INPUT my algorithm works slow. I unfortunately don't know the input data, but 6 from 12 tests finished with the wrong time. Maybe for some input data, some of the loops do not stop.

Where time is 1.01 or 2.01 -> wrong

wrong">


TASK


Consider any indexed sequence of natural numbers C, which define the
concept of the present position. Next, we introduce two operations on
the elements of this sequence: If amount of sequence of natural
numbers is even number ->


R, remove the item 'c' on index POS + 1, then move the pointer POS on
'c' elements to the right, otherways ->


X, inserting element 'c' on the position (POS + 1) value 'c-1' from
POS, and then moving the pointer on the POS 'c' elements to the right.


INPUT:


the number of times of repetition scheme of operations R and X, the
sequence of natural numbers 'C'


OUTPUT:


numbers after operations from the position of index


LIMITS


The time complexity of O (tn), where 'n' is the length of 'C' and 't'
- times of repetition operations R and X.

```
#include
#include
#define gc getchar_unlocked

struct Element
{
unsigned int c;
Element* next;
Element(unsigned int value)
{
c = value;
next = NULL;
}
};

void scan_integer(unsigned int* o )
{
unsigned int c = gc();
int x = 0;
for( ; ((c57)); c = gc() );

for( ;c>47 && cnext = new Element(tmp);
current = current->next;
elements++;
}
current->next = first;
current = first;
for(int i = 0; i c & 1)
{
value = current->c;
Element* newC = new Element(value-1);
newC->next = current->next;
current->next = newC;
elements++;

Let's start with the code style, even though not asked explicitly.

It says C++, but apart from using a constructor on the struct and using new/delete, that is pure C what you have written there.

Especially the C style input and output handling is overcomplicated, with regards to how much simpler the C++ interfaces are to use.

As for your implementation, you don't need a linked list. In fact, you don't need to store the input nor the output sequence at all, at least not for the algorithm itself.

Take a look at the problem carefully again, and try to think about how you can rephrase the operations, when do you need to consume input, and what the earliest point is, at which you can create output. Last but not least, how long do you even need to store each specific piece of information.

The first observation:

Whenever an operation has finished, the value at POS is no longer mutated, and no further insertions or deletions occur prior to POS.

The second observation:

During an operation at POS, no value other than POS has an effect on that operation. At most POS+1 is either removed or added in.

The third observation:

As all numbers are guaranteed to be natural numbers, even c - 1 > 0 must hold. Which means that in any case, POS+1 is always output in the same operation as which it is mutated in.

With that in mind, it's actually quite simple to solve this problem:

#include 
#include 

int main()
{
    std::vector input;
    int rounds = 0;
    bool even = false;

    // Collect the input
    std::cin >> rounds;
    int temp;
    while(std::cin >> temp) {
        input.push_back(temp);
    }

    even = (input.size() % 2) == 0;

    std::vector::iterator it = input.begin();

    // Special handling for first element
    std::cout << *it;
    it++;

    for(int round = 0; round < rounds; round++) {
        // Number of steps to the right
        int steps = *it;
        if(even) {
            // Operation "R"
            // Skip one
            it++;
            // And pass through from input
            for(int i = 0; i < steps; i++, it++) {
                std::cout << " " << *it;
            }
        } else {
            // Operation "X"
            // Directly output `POS+1`
            std::cout <<  " " << *it - 1;
            // But pass through one less input in return
            for(int i = 0; i < steps - 1; i++, it++) {
                std::cout <<  " " << *it;
            }
        }
        even != even;   
    }
    for(; it != input.end(); it++) {
        std::cout <<  " " << *it;
    }
}

It is unfortunately still necessary to store the entire input in memory, in order to count the elements. If it wasn't for that, you could just copy from input to output element wise.

But what's important: The data structure used is now a plain vector, which removes a lot of unnecessary stress on the memory system, as the storage method is a compact as it gets.

There are also no mutations to that data structure at all, it only serves to replay the input after counting all elements.

StackExchange Code Review Q#148574, answer score: 2