Submission #462404

#	Time	Username	Problem	Language	Result	Execution time	Memory
462404		rainboy	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	8 ms	344 KiB

mushrooms

/* https://ioi2020.sg/wp-content/uploads/sites/4/2020/09/mushrooms-solutions-ISC.pdf */
#include "mushrooms.h"
#include <ctype.h>
#include <stdio.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 20000, K = 45, C = 5, B = 1 << C, Q = 3, M = 171903, L = 10, T = 2 * L * L * L;

int queries(int k) {
	int q = k * 2 + 1, n = k * C + 1;

	while (n < N) {
		n += (k * C + 1 + q - (k * 2 + 1) + 1) / 2;
		q++;
	}
	return q;
}

void print_K() {
	int k;

	for (k = 1; k * C <= N; k++)
		if (queries(k) <= 226)
			printf("%d: %d\n", k, queries(k));
}

char ss[M][L + 1], cc[L + 1]; int ll[M], m;

void generate_(int b, int x, int y, int l) {
	int i;

	if (l > 0)
		strcpy(ss[m], cc), ll[m] = l, m++;
	for (i = 0; i < C; i++)
		if ((b & 1 << i) != 0)
			cc[l] = i + 'A', generate_(b ^ 1 << i, x, y, l + 1);
	if (x > 0)
		cc[l] = '0', generate_(b, x - 1, y, l + 1);
	if (y > 0)
		cc[l] = '1', generate_(b, x, y - 1, l + 1);
	cc[l] = 0;
}

int use_machine_(int h, int b) {
	int i, cnt;

	cnt = 0;
	for (i = 0; i + 1 < ll[h]; i++) {
		int x = isdigit(ss[h][i]) ? ss[h][i] - '0' : b >> ss[h][i] - 'A' & 1;
		int y = isdigit(ss[h][i + 1]) ? ss[h][i + 1] - '0' : b >> ss[h][i + 1] - 'A' & 1;

		if (x != y)
			cnt++;
	}
	return cnt;
}

int branch(char ss_[][L + 1], int t, int q, long long mask) {
	static long long masks[Q + 1][L];
	int h, i, b, k;

	if (mask == 0) {
		ss_[t][0] = 0;
		return 1;
	}
	if ((mask & mask - 1) == 0) {
		for (b = 0; b < B; b++)
			if ((mask & 1LL << b) != 0) {
				ss_[t][0] = '[', ss_[t][C + 1] = ']', ss_[t][C + 2] = 0;
				for (i = 0; i < C; i++)
					ss_[t][i + 1] = (b >> i & 1) + '0';
				break;
			}
		return 1;
	}
	if (q == 0)
		return 0;
	for (h = 0; h < m; h++) {
		int good;

		if (q == 3 && ll[h] != 6)
			continue;
		memset(masks[q], 0, L * sizeof *masks[q]);
		for (b = 0; b < B; b++)
			if ((mask & 1LL << b) != 0)
				masks[q][use_machine_(h, b)] |= 1LL << b;
		good = 1;
		for (k = 0; k < L; k++)
			if (!branch(ss_, t * L + k, q - 1, masks[q][k])) {
				good = 0;
				break;
			}
		if (good) {
			strcpy(ss_[t], ss[h]);
			return 1;
		}
	}
	return 0;
}

void print(char ss_[][L + 1], int t) {
	int k;

	if (ss_[t][0] == 0)
		return;
	printf("%d: %s\n", t, ss_[t]);
	if (ss_[t][0] == '[')
		return;
	for (k = 0; k < L; k++)
		print(ss_, t * L + k);
}

char ss103[T][L + 1];

void build103() {
	m = 0, generate_(B - 1, 1, 0, 0);
	branch(ss103, 1, 3, (1LL << 32) - 1);
#if 0
	print(ss103, 1);
#endif
}

char ss212[T][L + 1];

void build212() {
#if 0
	m = 0, generate_(B - 1, 3, 1, 0);
	branch(ss212, 1, 2, (1LL << 32) - 1);
	print(ss212, 1);
#else
	strcpy(ss212[1], "ABC0D0E");
	strcpy(ss212[10], "[00000]");
	strcpy(ss212[11], "AB1C");
	strcpy(ss212[110], "[11100]");
	strcpy(ss212[111], "[11000]");
	strcpy(ss212[112], "[00001]");
	strcpy(ss212[113], "[10000]");
	strcpy(ss212[12], "A0B0ED1C");
	strcpy(ss212[121], "[00100]");
	strcpy(ss212[122], "[00010]");
	strcpy(ss212[123], "[01100]");
	strcpy(ss212[124], "[01000]");
	strcpy(ss212[125], "[10001]");
	strcpy(ss212[126], "[11101]");
	strcpy(ss212[127], "[11001]");
	strcpy(ss212[13], "BE10A0D0C");
	strcpy(ss212[131], "[01001]");
	strcpy(ss212[132], "[01101]");
	strcpy(ss212[133], "[00101]");
	strcpy(ss212[134], "[00011]");
	strcpy(ss212[135], "[10100]");
	strcpy(ss212[136], "[10010]");
	strcpy(ss212[137], "[11010]");
	strcpy(ss212[138], "[11110]");
	strcpy(ss212[14], "A0E0DC1B");
	strcpy(ss212[141], "[01110]");
	strcpy(ss212[142], "[00110]");
	strcpy(ss212[143], "[01010]");
	strcpy(ss212[144], "[11111]");
	strcpy(ss212[145], "[10101]");
	strcpy(ss212[146], "[11011]");
	strcpy(ss212[147], "[10011]");
	strcpy(ss212[15], "AB0DC");
	strcpy(ss212[151], "[00111]");
	strcpy(ss212[152], "[10110]");
	strcpy(ss212[153], "[01111]");
	strcpy(ss212[154], "[01011]");
	strcpy(ss212[16], "[10111]");
#endif
}

vi ii; int ii0[N], ii1[N], n0, n1;

void solve(char ss_[][L + 1], int i, int flip) {
	int t = 1;

	while (1)
		if (ss_[t][0] == '[') {
			for (i = 0; i < 5; i++)
				if ((ss_[t][i + 1] - '0' ^ flip) == 0)
					ii0[n0++] = i;
				else
					ii1[n1++] = i;
			return;
		} else {
			int l = strlen(ss_[t]), h, h0, h1;

			ii.resize(l);
			for (h = 0, h0 = 0, h1 = 0; h < l; h++)
				if (isdigit(ss_[t][h]))
					ii[h] = (ss_[t][h] - '0' ^ flip) == 0 ? ii0[h0++] : ii1[h1++];
				else
					ii[h] = i * 5 + ss_[t][h] - 'A' + 1;
			t = t * L + use_machine(ii);
		}
}

int count_mushrooms(int n) {
	int n_, h, i, k, ans;

	build103(), build212();
	if (n < K * 5 + 1) {
		ans = n;
		for (i = 1; i < n; i++)
			ii.resize(2), ii[0] = 0, ii[1] = i, ans -= use_machine(ii);
	} else {
		ii0[n0++] = 0;
		for (i = 0; i < K; i++)
			if (n1 == 0)
				solve(ss103, i, 0);
			else
				solve(ss212, i, n0 >= 3 ? 0 : 1);
		i = K * 5 + 1;
		ans = n0;
		while (i < n)
			if (n0 > n1) {
				ii.resize(0);
				for (h = 0; h < n0; h++) {
					ii.push_back(ii0[h]);
					if (i < n)
						ii.push_back(i++);
				}
				n_ = ii.size();
				k = use_machine(ii);
				if (n_ == n0 * 2) {
					if (k % 2 == 1)
						ii1[n1++] = ii[--n_], k--;
					else
						ii0[n0++] = ii[n_ - 1], ans++;
				}
				ans += n_ - n0 - k / 2;
			} else {
				ii.resize(0);
				for (h = 0; h < n1; h++) {
					ii.push_back(ii1[h]);
					if (i < n)
						ii.push_back(i++);
				}
				n_ = ii.size();
				k = use_machine(ii);
				if (n_ == n1 * 2) {
					if (k % 2 == 1)
						ii0[n0++] = ii[--n_], ans++, k--;
					else
						ii1[n1++] = ii[n_ - 1];
				}
				ans += k / 2;
			}
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int use_machine_(int, int)':
mushrooms.cpp:53:62: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   53 |   int x = isdigit(ss[h][i]) ? ss[h][i] - '0' : b >> ss[h][i] - 'A' & 1;
      |                                                     ~~~~~~~~~^~~~~
mushrooms.cpp:54:74: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   54 |   int y = isdigit(ss[h][i + 1]) ? ss[h][i + 1] - '0' : b >> ss[h][i + 1] - 'A' & 1;
      |                                                             ~~~~~~~~~~~~~^~~~~
mushrooms.cpp: In function 'int branch(char (*)[11], int, int, long long int)':
mushrooms.cpp:70:19: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   70 |  if ((mask & mask - 1) == 0) {
      |              ~~~~~^~~
mushrooms.cpp: In function 'void solve(char (*)[11], int, int)':
mushrooms.cpp:184:24: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  184 |     if ((ss_[t][i + 1] - '0' ^ flip) == 0)
      |          ~~~~~~~~~~~~~~^~~~~
mushrooms.cpp:195:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  195 |      ii[h] = (ss_[t][h] - '0' ^ flip) == 0 ? ii0[h0++] : ii1[h1++];
      |               ~~~~~~~~~~^~~~~

• Subtask 1: 0 / 100