Firstly, huge thanks to Noam527 for guiding me to this solution by providing his output for N = 255. This probably wouldn't have been possible without his help.

As some of you may know, getting 100 points for IOI 2003 Reverse is pretty difficult. The editorial only explains an 88-point solution and there seemed to be no publicly available code online that scored 100 points.

This blog post serves as a tutorial for those who are stuck with 88 points (or less) but who would like 100 points (to fill in that last yellow cell on OIChecklist or just to flex).

88-point solution

I'll just quote the editorial for this solution.

Consider the case of trying to solve each input with only one S-operation. Clearly, register 1 might as well as be initialized to N. The register 2 can be N - 2. After printing out N, one S-operation turns register 1 to N - 1. Register 3 can be N - 5. After printing N - 2, S 3 1 makes register 1 N - 4. After printing out N - 2, S 1 2 turns register 2 into N - 3, the next value to output. Continuing this through all the registers, 44 is the largest value of N which can be solved in only one S-operation.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, k, reg[9];
int lim[8]{8, 44, 80, 116, 152, 188, 224, 260};

void INIT(int V, int P) {
    printf("%d", V);
    if (P == 8) printf("\n");
    else printf(" ");
    reg[P] = V;
}

void ADD(int A, int B) {
    reg[B] = reg[A] + 1;
    printf("S %d %d\n", A + 1, B + 1);
}

int FIND(int V) { return find(reg, reg + 9, V) - reg; }

void PRINT(int P) { printf("P %d\n", P + 1); }

int main() {
    scanf("%d %d", &k, &n);
    printf("FILE reverse %d\n", k);

    int mx = lower_bound(lim, lim + 8, n) - lim;

    int c = n;
    FOR(i, 0, 9) {
        INIT(max(0, c), i);
        c -= mx * i + mx + 1;
    }

    int nxt = 1, curr = -1, rising = 1;
    n++;
    while (n--) {
        int pos = FIND(n);
        if (pos == 9) {
            FOR(i, 1, mx + 1) {
                pos = FIND(n - i);
                if (pos != 9) {
                    ADD(pos, curr);
                    FOR(j, 1, i) ADD(curr, curr);
                    PRINT(curr);
                    break;
                }
            }
        } else {
            if (pos == rising && nxt != 8) rising = ++nxt;
            if (~curr && mx && reg[rising] + mx < n) {
                ADD(rising, curr);
                FOR(i, 1, mx) ADD(curr, curr);
                rising = curr;
            }
            PRINT(pos);
            curr = pos;
        }
    }
    return 0;
}

The code for 88 points is pretty clean and elegant. Most people would stop here. However, if you hate yourself want a challenge, then you'd probably try to get 100 points.

100-point solution

The 100-point solution is a relatively simple extension of the 88-point solution.

With the 88-point solution, the only test cases where you won't get AC are probably the cases with N = 97 (MAX_S = 2) or N > 188 (MAX_S = 4).

Consider the output of the 88-point code for N = 97 (the optimal MAX_S is 2; the MAX_S here is 3):

97 93 86 76 63 47 28 6 0
P 1
S 2 1
S 1 1
S 1 1
P 1
S 2 1
S 1 1
P 1
S 2 1
P 1
S 3 1
S 1 1
S 1 1
P 2
S 1 2
S 2 2
S 2 2
P 2
S 1 2
S 2 2
P 2
S 1 2
P 2
etc.

Notice anything inefficient?

That's right — we can use up to 3 consecutive S-operations but there are many places where we only use 1 or 2 consecutive S-operations. Moreover, we can increment any of the 9 values but for each block of consecutive S-operations, we only increase 1.