oj.uz

Submission #467391

# Submission time Handle Problem Language Result Execution time Memory
467391 2021-08-22T22:17:19 Z rainboy Reverse (IOI03_reverse) Text
86.3 / 100
 0 ms 0 KB 
#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;
}

Subtask #1
0 / 6.0

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

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
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 #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

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

Subtask #10
6.0 / 6.0

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

Subtask #11
6.0 / 6.0

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

Subtask #12
6.0 / 6.0

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

Subtask #13
7.0 / 7.0

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

Subtask #14
5.6 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 0 KB OK. Jury MAX_S: 4. Participant MAX_S: 5

Subtask #15
4.2 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 0 KB OK. Jury MAX_S: 4. Participant MAX_S: 6

Subtask #16
3.5 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 0 KB OK. Jury MAX_S: 4. Participant MAX_S: 7