Submission #395606

#	Time	Username	Problem	Language	Result	Execution time	Memory
395606		rainboy	Scales (IOI15_scales)	C11	100 / 100	32 ms	328 KiB

scales

/* upsolve after reading analysis */
#include "scales.h"
#include <string.h>

#define N	6
#define M	720
#define N_	1093
#define K	6

int p3[] = { 1, 3, 9, 27, 81, 243, 729 };

int next_permutation(int *pp) {
	int i, j, tmp;

	i = N - 2;
	while (i >= 0 && pp[i] > pp[i + 1])
		i--;
	if (i < 0)
		return 0;
	j = N - 1;
	while (j > 0 && pp[i] > pp[j])
		j--;
	tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
	for (i++, j = N - 1; i < j; i++, j--)
		tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
	return 1;
}

int ppp[M][N]; char type[K + 1][M];
int mode_[N_], aa[N_], bb[N_], cc[N_], dd[N_];

int query(int *pp, int mode, int a, int b, int c, int d) {
	if (mode == 3) {
		if (pp[d] > pp[a] && pp[d] > pp[b] && pp[d] > pp[c])
			mode = 0;
		else {
			if (pp[a] > pp[d] && (pp[b] < pp[d] || pp[b] > pp[a]) && (pp[c] < pp[d] || pp[c] > pp[a]))
				return 1;
			if (pp[b] > pp[d] && (pp[a] < pp[d] || pp[a] > pp[b]) && (pp[c] < pp[d] || pp[c] > pp[b]))
				return 2;
			return 3;
		}
	}
	if (mode == 0) {
		if (pp[a] < pp[b] && pp[a] < pp[c])
			return 1;
		if (pp[b] < pp[a] && pp[b] < pp[c])
			return 2;
		return 3;
	}
	if (mode == 1) {
		if (pp[a] > pp[b] && pp[a] > pp[c])
			return 1;
		if (pp[b] > pp[a] && pp[b] > pp[c])
			return 2;
		return 3;
	}
	if (mode == 2) {
		if ((pp[a] > pp[b]) != (pp[a] > pp[c]))
			return 1;
		if ((pp[b] > pp[a]) != (pp[b] > pp[c]))
			return 2;
		return 3;
	}
	return -1;
}

int dfs(int u, int k) {
	static int cnt[4];
	int h, h_;

	h_ = -1;
	for (h = 0; h < M; h++)
		if (type[k][h]) {
			if (h_ == -1)
				h_ = h;
			else {
				h_ = -2;
				break;
			}
		}
	if (h_ == -1)
		return 1;
	if (h_ != -2) {
		mode_[u] = -h_ - 1;
		return 1;
	}
	for (mode_[u] = 0; mode_[u] < 4; mode_[u]++)
		for (aa[u] = 0; aa[u] < N; aa[u]++)
			for (bb[u] = aa[u] + 1; bb[u] < N; bb[u]++)
				for (cc[u] = bb[u] + 1; cc[u] < N; cc[u]++)
					for (dd[u] = 0; dd[u] < (mode_[u] == 3 ? N : 1); dd[u]++) {
						int t, ok;

						if (mode_[u] == 3 && (dd[u] == aa[u] || dd[u] == bb[u] || dd[u] == cc[u]))
							continue;
						cnt[1] = cnt[2] = cnt[3] = 0;
						for (h = 0; h < M; h++)
							if (type[k][h])
								cnt[type[k][h] = query(ppp[h], mode_[u], aa[u], bb[u], cc[u], dd[u])]++;
						if (cnt[1] > p3[K - 1 - k] || cnt[2] > p3[K - 1 - k] || cnt[3] > p3[K - 1 - k])
							continue;
						ok = 1;
						for (t = 1; t <= 3; t++) {
							for (h = 0; h < M; h++)
								type[k + 1][h] = type[k][h] == t;
							if (!dfs(u * 3 + t, k + 1)) {
								ok = 0;
								break;
							}
						}
						if (ok)
							return 1;
					}
	return 0;
}

void init(int T) {
	static int pp[N];
	int i, m;

	for (i = 0; i < N; i++)
		pp[i] = i;
	m = 0;
	do {
		memcpy(ppp[m++], pp, N * sizeof *pp);
	} while (next_permutation(pp));
	memset(type[0], 1, M * sizeof *type[0]);
	dfs(0, 0);
}

void orderCoins() {
	static int ans[N];
	int h, i, u;

	u = 0;
	while (mode_[u] >= 0) {
		int x;

		if (mode_[u] == 0)
			x = getLightest(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
		else if (mode_[u] == 1)
			x = getHeaviest(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
		else if (mode_[u] == 2)
			x = getMedian(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
		else
			x = getNextLightest(aa[u] + 1, bb[u] + 1, cc[u] + 1, dd[u] + 1) - 1;
		if (x == aa[u])
			u = u * 3 + 1;
		else if (x == bb[u])
			u = u * 3 + 2;
		else
			u = u * 3 + 3;
	}
	h = -1 - mode_[u];
	for (i = 0; i < 6; i++)
		ans[ppp[h][i]] = i + 1;
	answer(ans);
}

Compilation message (stderr)

scales.c: In function 'dfs':
scales.c:100:26: warning: conversion from 'int' to 'char' may change value [-Wconversion]
  100 |         cnt[type[k][h] = query(ppp[h], mode_[u], aa[u], bb[u], cc[u], dd[u])]++;
      |                          ^~~~~
scales.c:100:24: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |         cnt[type[k][h] = query(ppp[h], mode_[u], aa[u], bb[u], cc[u], dd[u])]++;
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.c: In function 'init':
scales.c:118:15: warning: unused parameter 'T' [-Wunused-parameter]
  118 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100