- One possible correct output for H1
- One possible correct output for H2
- C++ program to check submissions

In the easy subproblem, we can have multiple commands on one line separated by semicolons. The stack is initially empty but can stay non-empty when the program ends, so we can use the `push`

command to determine the line order after sorting. The pushed values are ignored otherwise. For example, the following structure works:

```
push 1;... subroutine for x -> x ...;jump 3
push 0;... subroutine for x -> -x ...;jump 3
push 2;... subroutine for x -> x * x ...;jump 3
```

In the normal case, the subroutine for *x* is executed and then the execution jumps to the line number 3, which means the program exits. In the reversed case, the subroutine for *x*^{2} is executed. Finally, in the sorted case the second line becomes the first and the subroutine for −*x* is executed. The subroutines are respectively:

```
input;print
input;push -1;*;print
input;dup;*;print
```

The full program then becomes:

```
push 1;input;print;jump 3
push 0;input;push -1;*;print;jump 3
push 2;input;dup;*;print;jump 3
```

Arithmetic operations come before letters in the ASCII table. Also the `dup`

command comes before all other word commands, so arithmetic operations together with `dup`

are always first in the sorted order. However, all these operations crash with an empty stack and we don’t get a chance to push anything onto the top of the stack before we execute them, so we cannot have lines starting with arithmetic operations or `dup`

.

A trick to execute such operations is to wrap them in “`push ?`

” and `pop`

. E.g. for `+`

we have:

```
push 42
pop;+
```

The general idea of the solution is to have 3 areas of the program separated by “`jump 99`

” commands (assuming the program has 99 lines):

```
... subroutine for x -> x ...
...;jump 99
... extra lines for x -> -x ...
...;jump 99
... subroutine for x -> x * x when reversed ...
```

Let’s label these 3 areas *α*, *β* and *γ* respectively. For *γ*, we can use the following sequence of commands (showed in reversed order for clarity).

```
input;dup
push ?
pop;*
print;jump 99
```

If there are multiple `input`

commands in the program, we need to make sure only one gets executed each time. One line can start with `input`

and another can contain “`push ?;input`

”. A `jump`

command between them makes sure only one of them gets executed. As “`input;dup`

” is already in *γ*, we use “`push ?;input`

” in *α*. The whole *α* then becomes:

```
push ?;input
print;jump 99
```

We know that “`input;dup`

” ends up at the beginning of the sorted program. A `jump`

command comes lexicographically right after `input`

, so we can add it to *β* and use it to jump to the part calculating −*x* in the sorted program. The jump can go to a line starting with `pop`

, `print`

or `push`

. Jumping to a `print`

would be wrong, since we have *x* at the top of the stack at that point. Instead, we can calculate −*x* by pushing −1 onto the stack and then multiplying the two top-most elements. So we point `jump`

to the line “`push -1;*`

”, which we add to *β*.

The lines that follow in the sorted order after “`push -1;*`

” start with `push`

commands, which don’t allow us to print −*x* that is at the top of the stack, we jump back in the program using “`push z;jump`

ℓ”, where ℓ is a line higher up in the program. We just pushed *z* to the stack, so the line we jump to starts with `pop`

. We want the line that comes after popping *z* from stack to be “`print;jump 99`

”, so the line popping *z* must come lexicographically after “`pop;*`

” (from *γ*). We achieve it by using “`pop;jump`

ℓ + 1”, which effectively continues on the next line.

To recapitulate, we have the following lines in *β*:

```
jump L # Line number to be determined
push -1;*
push ?;jump K # Line number to be determined
pop;jump K+1
```

Putting all pieces together, the program looks as follows (with line numbers for clarity):

```
0: push 2;input
1: print;jump 10
2: jump 6
3: push -1;*
4: push 1;jump 3
5: pop;jump 4
6: print;jump 10
7: pop;*
8: push 3
9: input;dup
```

The sorted program is the following:

```
0: input;dup
1: jump 6
2: pop;*
3: pop;jump 4
4: print;jump 10
5: print;jump 10
6: push -1;*
7: push 1;jump 3
8: push 2;input
9: push 3
```