Submission #467418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467418	2021-08-22T22:28:51 Z	rainboy	Reverse (IOI03_reverse)	Text	36 / 100	0 ms	0 KB

reverse-out-01

FILE reverse 1
0 1 2 3 4 5 6 7 8 
P 3
P 2
P 1

reverse-out-02

FILE reverse 2
0 1 2 3 4 5 6 7 8 
P 9
P 8
P 7
P 6
P 5
P 4
P 3
P 2
P 1

reverse-out-03

FILE reverse 3
0 9 1 10 2 11 3 12 4 
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 2
S 4 2
P 2
P 4
P 6
P 8
P 9
P 7
P 5
P 3
P 1

reverse-out-04

FILE reverse 4
0 9 1 10 2 11 14 12 13 
P 7
S 5 7
P 9
S 7 9
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 2
S 4 2
P 2
P 4
P 6
P 8
P 9
P 7
P 5
P 3
P 1

reverse-out-05

FILE reverse 5
0 9 17 24 18 25 19 26 20 
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 4
S 2 4
P 6
S 4 6
P 8
S 6 8
P 9
S 8 9
P 7
S 9 7
P 5
S 7 5
P 3
S 5 3
P 3
S 1 3
P 5
S 3 5
P 7
S 5 7
P 9
S 7 9
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 2
S 4 2
P 2
P 4
P 6
P 8
P 9
P 7
P 5
P 3
P 1

reverse-out-06

FILE reverse 6
0 9 17 24 30 25 31 33 32 
P 8
S 6 8
P 9
S 8 9
P 7
S 9 7
P 5
S 7 5
P 5
S 3 5
P 7
S 5 7
P 9
S 7 9
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 4
S 2 4
P 6
S 4 6
P 8
S 6 8
P 9
S 8 9
P 7
S 9 7
P 5
S 7 5
P 3
S 5 3
P 3
S 1 3
P 5
S 3 5
P 7
S 5 7
P 9
S 7 9
P 8
S 9 8
P 6
S 8 6
P 4
S 6 4
P 2
S 4 2
P 2
P 4
P 6
P 8
P 9
P 7
P 5
P 3
P 1

reverse-out-07

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-08

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-09

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-10

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-11

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-12

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-13

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-14

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-15

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

reverse-out-16

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N	9

int min(int a, int b) { return a < b ? a : b; }

int ii[N], jj[N], aa[N], bb[N];

void display() {
	int i;

	for (i = 0; i < N; i++)
		printf("%d ", aa[i]);
	printf("\n");
}

int a_, active, limit, run;

void P(int i) {
	run = 0;
	if (a_ >= aa[i]) {
		assert(a_-- == aa[i]);
		if (!active)
			active = 1, display();
		printf("P %d\n", i + 1);
	}
}

void S(int i, int j) {
	if (active)
		printf("S %d %d\n", i + 1, j + 1);
	aa[j] = aa[i] + 1;
	assert(i < N && j < N && ++run <= limit);
}

void Q(int lower, int k, int l, int n, int d_) {
	int m, h, h_, d, d1, partial;

	assert(k + l < n);
	m = k + l;
	if (k > 0)
		k--;
	else
		l--;
	for (h = 0; h < m; h++) {
		bb[h] = lower;
		if (h + 1 < m) {
			if (k > 0)
				lower += d_ + 1, k--;
			else
				lower += d_, l--;
		}
	}
	partial = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
			for (d1 = d; d1 < d_; d1++)
				if (h_ < h) {
					if (!partial)
						S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
					else
						S(ii[n - 1 - h_], ii[n - 1 - h_]);
					if (aa[ii[n - 1 - h_]] == bb[h_])
						h_++, partial = 0;
				}
			P(ii[n - 1 - h]);
		}
		for (d1 = 0; d1 < d_; d1++)
			if (h_ <= h) {
				if (!partial)
					S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
				else
					S(ii[n - 1 - h_], ii[n - 1 - h_]);
				if (aa[ii[n - 1 - h_]] == bb[h_])
					h_++, partial = 0;
			}
		P(ii[n - 2 - h]);
	}
	for (h = 0; h < m; h++)
		jj[h] = ii[n - 1 - h];
	for (h = m; h < n; h++)
		jj[h] = ii[h - m];
	for (h = 0; h < n; h++)
		ii[h] = jj[h];
}

int simulate(int k, int l, int n, int d_, int upper) {
	int k_, l_, h;

	if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
		return 0;
	for ( ; k + l > 0; k = k_, l = l_) {
		k_ = k, l_ = l;
		if (k_ > 0)
			k_--;
		else
			l_--;
		if (k_ + l_ > 0) {
			if (l_-- == 0)
				return 0;
			k_ -= n - 3;
			if (k_ < 0)
				l_ += k_, k_ = 0;
			if (l_ < 0)
				l_ = 0;
		}
		if (upper >= 0) {
			if (k_ + l_ > 0)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
			else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
				Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
			else
				Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
		}
	}
	if (upper >= 0) {
		for (h = n; h > 0; h--)
			ii[h] = ii[h - 1];
		ii[0] = N - 1 - n;
	}
	return 1;
}

int solve(int a, int d_) {
	static int kk[N], ll[N];
	int i, k, l, d, d1;

	aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
	for (i = N - 4; i >= 0; i--) {
		kk[i] = 0, ll[i] = 0;
		for (k = 1; k <= 100; k++)
			for (l = 0; l <= 100; l++)
				if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
					kk[i] = k, ll[i] = l;
		aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
	}
	if (aa[0] < a)
		return 0;
	for (i = 1; i < N; i++)
		aa[i] = aa[0] - aa[i];
	aa[0] = 0;
	limit = d_;
	a_ = a, active = 0;
	P(N - 1);
	for (d = d_; d > 0; d--) {
		for (d1 = 0; d1 < d; d1++)
			S(d1 == 0 ? N - 2 : N - 1, N - 1);
		P(N - 1);
	}
	for (d1 = 0; d1 < d_; d1++)
		S(d1 == 0 ? N - 3 : N - 1, N - 1);
	P(N - 2);
	ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
	for (i = N - 4; i >= 0; i--)
		simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
	for (i = N - 2; i >= 0; i--) {
		for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
			for (d1 = 0; d1 < d; d1++)
				S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
			P(ii[i + 1]);
		}
		P(ii[i]);
	}
	assert(a_ == -1);
	return 1;
}

int main() {
	int t, a, i, d_;

	scanf("%d%d", &t, &a);
	printf("FILE reverse %d\n", t);
	if (a < N) {
		for (i = 0; i < N; i++)
			printf("%d ", i);
		printf("\n");
		for (i = a; i >= 0; i--)
			printf("P %d\n", i + 1);
		return 0;
	}
	d_ = 1;
	while (!solve(a, d_))
		d_++;
	return 0;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 0. Participant MAX_S: 0

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 0. Participant MAX_S: 0

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 1. Participant MAX_S: 1

Subtask #4

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 1. Participant MAX_S: 1

Subtask #5

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 1. Participant MAX_S: 1

Subtask #6

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	0 KB	OK. Jury MAX_S: 1. Participant MAX_S: 1

Subtask #7

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #8

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #9

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #10

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #11

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #12

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #13

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #14

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #15

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed

Subtask #16

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	0 KB	Presentation Error: First Line is Malformed