Submission #795875

#	Time	Username	Problem	Language	Result	Execution time	Memory
795875		rainboy	Present (RMI21_present)	C11	100 / 100	40 ms	46456 KiB

Main

/* upsolve with help from PurpleCrayon */
#include <stdio.h>

#define A	38
#define U	(1 << A / 2)

int gcd[A + 1][A + 1], mx[U], bb[A / 2], ban_odd[U], kk_even[A / 2 + 1][U]; char good_odd[U], good_even[U];

void init() {
	int a, b, c, i, j, k, u, u_, v, v_;

	for (a = 0; a <= A; a++)
		for (b = 0; b <= A; b++)
			gcd[a][b] = a > b ? gcd[b][a] : a == 0 ? b : gcd[b % a][a];
	for (u = 1, i = 0; u < U; u++) {
		while (1 << i + 1 <= u)
			i++;
		mx[u] = i;
	}
	good_odd[0] = 1, ban_odd[0] = 0;
	for (j = 0; j < A / 2; j++) {
		b = j * 2 + 1;
		good_odd[1 << j] = 1;
		for (u = 1; u < 1 << j; u++) {
			u_ = u | 1 << j, i = mx[u], a = i * 2 + 1;
			good_odd[u_] = good_odd[u_ ^ 1 << i] && (u & 1 << (gcd[a][b] - 1) / 2) != 0;
		}
		for (i = 0; i < A / 2; i++) {
			a = i * 2 + 1;
			bb[i] = 0;
			for (k = 0; k < A / 2; k++) {
				c = k * 2 + 2;
				if (gcd[b][c] == a)
					bb[i] |= 1 << k;
			}
		}
		for (u = (1 << j) - 2; u >= 0; u--) {
			u_ = u | 1 << j, i = mx[(1 << j) - 1 ^ u];
			ban_odd[u_] = ban_odd[u_ ^ 1 << i] | bb[i];
		}
		for (u = 0; u < 1 << j; u++) {
			u_ = u | 1 << j;
			good_odd[u_] &= good_odd[u], ban_odd[u_] |= ban_odd[u];
		}
	}
	good_even[0] = 1;
	for (j = 0; j < A / 2; j++) {
		b = j * 2 + 2;
		good_even[1 << j] = 1;
		for (v = 1; v < 1 << j; v++) {
			v_ = v | 1 << j, i = mx[v], a = i * 2 + 2;
			good_even[v_] = good_even[v_ ^ 1 << i] && (v & 1 << (gcd[a][b] - 1) / 2) != 0;
		}
		for (v = 0; v < 1 << j; v++) {
			v_ = v | 1 << j;
			good_even[v_] &= good_even[v];
		}
	}
	for (v = 0; v < 1 << A / 2; v++)
		kk_even[0][v] = good_even[v];
	for (j = 0; j < A / 2; j++)
		for (v = 0; v < 1 << A / 2; v++) {
			kk_even[j + 1][v] = kk_even[j][v];
			if ((v & 1 << j) != 0)
				kk_even[j + 1][v] += kk_even[j][v ^ 1 << j];
		}
}

int main() {
	int t;

	init();
	scanf("%d", &t);
	while (t--) {
		int k, i, u, u_, u0, u1, v_, v0, v1, l, k00, k01, k10, k11;

		scanf("%d", &k);
		u_ = 0, v_ = 0, l = 0;
		for (i = A / 2 - 1; i >= 0; i--) {
			u0 = u_, u1 = u_ | 1 << i, v0 = v_, v1 = v_ | 1 << i;
			k00 = k01 = k10 = k11 = 0;
			for (u = 0; u < 1 << i; u++) {
				if (good_odd[u0 | u] && (ban_odd[u0 | u] & v0) == 0)
					k00 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u0 | u]];
				if (good_odd[u1 | u] && (ban_odd[u1 | u] & v0) == 0)
					k01 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u1 | u]];
				if (good_odd[u0 | u] && (ban_odd[u0 | u] & v1) == 0)
					k10 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u0 | u]];
				if (good_odd[u1 | u] && (ban_odd[u1 | u] & v1) == 0)
					k11 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u1 | u]];
			}
			if (k < k00) {
				u_ = u0, v_ = v0, l += 0;
				continue;
			}
			k -= k00;
			if (k < k01) {
				u_ = u1, v_ = v0, l += 1;
				continue;
			}
			k -= k01;
			if (k < k10) {
				u_ = u0, v_ = v1, l += 1;
				continue;
			}
			k -= k10;
			u_ = u1, v_ = v1, l += 2;
		}
		printf("%d", l);
		for (i = 0; i < A / 2; i++) {
			if ((u_ & 1 << i) != 0)
				printf(" %d", i * 2 + 1);
			if ((v_ & 1 << i) != 0)
				printf(" %d", i * 2 + 2);
		}
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'init':
Main.c:16:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   16 |   while (1 << i + 1 <= u)
      |               ~~^~~
Main.c:38:37: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   38 |    u_ = u | 1 << j, i = mx[(1 << j) - 1 ^ u];
      |                            ~~~~~~~~~^~~
Main.c: In function 'main':
Main.c:84:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   84 |      k00 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u0 | u]];
      |                             ~~~~~~~~~^~~
Main.c:84:42: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   84 |      k00 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u0 | u]];
      |                             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
Main.c:86:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   86 |      k01 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u1 | u]];
      |                             ~~~~~~~~~^~~
Main.c:86:42: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   86 |      k01 += kk_even[i][v0 | (1 << i) - 1 & ~ban_odd[u1 | u]];
      |                             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
Main.c:88:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   88 |      k10 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u0 | u]];
      |                             ~~~~~~~~~^~~
Main.c:88:42: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   88 |      k10 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u0 | u]];
      |                             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
Main.c:90:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   90 |      k11 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u1 | u]];
      |                             ~~~~~~~~~^~~
Main.c:90:42: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   90 |      k11 += kk_even[i][v1 | (1 << i) - 1 & ~ban_odd[u1 | u]];
      |                             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
Main.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
Main.c:77:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &k);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16