LR Springboard

Hyungchan manages the Spring Yard attraction at an amusement park. The attraction is a row of $N$ springs. When a person steps on a spring, they bounce up and land on the spring next to it. When this repeats, the audience feels thrills and the rider feels excitement. If a person bounces left from the leftmost spring or right from the rightmost spring, they fall onto a mat and the turn ends.

Every spring leans slightly to the left or the right. Stepping on a spring sends the person up in the direction that spring faces. After a person bounces off a spring, that spring flips its direction. A spring facing left turns to face right, and a spring facing right turns to face left.

It is getting dark, so Hyungchan wants to pack up the attraction. Park policy requires every spring to face left. Hyungchan must not change the springs by hand because of the safety risk, so he uses blue balls to change their directions.

When Hyungchan drops a ball from high up, the ball bounces around and lands on the left end mat or the right end mat. As the figure shows, if he drops a ball on the 3rd spring and then on the 1st spring, every spring faces left.

From high up, Hyungchan cannot see which way each of the $N$ springs faces. He never knows the state of the springs. However, he can easily tell whether a dropped ball stops at the left end or the right end. Help Hyungchan drop balls in the right order so that every spring faces left. Write a program that does this.

You must write the function Reorder(N) that puts the springs in order. Reorder(N) is in springboard.c or springboard.cpp.

The argument of void Reorder(int N) is:

• $N$: the number of springs ($1 \le N \le 12\,345$)

Inside Reorder, you can call PutBall(K) several times.

int PutBall(int K) drops a ball on the K-th spring from the left.

• $K$: the position where the ball is dropped ($1 \le K \le N$)
• Return value: returns -1 if the ball leaves to the left, and 1 if it leaves to the right.

When Reorder(N) returns, every spring must face left. Otherwise the grader prints Wrong[1]. If an argument is out of range, the grader prints Wrong[2] and exits immediately. If you call PutBall(K) more times than allowed, the grader prints Wrong[3] and exits immediately.

PutBall(K) can be called at most $16$ times.

The grader fixes the initial arrangement of the springs before Reorder is called. It does not change the arrangement based on your calls (non-adaptive). Using memory access, system calls, or other abnormal methods may be judged wrong.

An example program is below. The comments show the return value of each call in the same situation.

#include "springboard.h"

void Reorder(int N) {
	PutBall(3); // return value = -1
	PutBall(1); // return value = 1
}

You can download the sample code from the problem page. If you use an IDE such as Visual Studio, Eclipse, or Code::Blocks, put springboard.cpp, springboard.h, and grader.cpp (or springboard.c, springboard.h, and grader.c) in one project and compile it. To compile in a terminal, use the commands below.

• C / gcc: gcc -Wall -lm -static -o springboard -O2 springboard.c grader.c
• C++ / G++: g++ -Wall -lm -static -o springboard -O2 springboard.cpp grader.cpp

When you run the program, it reads N and then the directions of the N springs from standard input. Each direction is a string of length N made of 'L' and 'R'. 'L' means the spring faces left, and 'R' means it faces right. After reading all the input, the sample grader prints whether the answer is correct.

Submit only springboard.c or springboard.cpp.