Submission #485400

#	Time	Username	Problem	Language	Result	Execution time	Memory
485400		rainboy	GTA (COI14_gta)	C11	0 / 100	3 ms	716 KiB

gta

/* upsolve after reading solution */
#include <stdio.h>
#include <string.h>

#define N	10000
#define L	2
#define L_	50000

char *acgt = "ACGT";

int rep[N + 1];

void init() {
	static int aa[L], bb[L], cc[L], pp4[L + 1], qu[N];
	int n, l, r, cnt;

	pp4[0] = 1;
	for (l = 1; l <= L; l++)
		pp4[l] = pp4[l - 1] * 4;
	n = 0;
	for (l = 1; l <= L; l++)
		n = n * 4 + 4;
	for (r = 1; r <= n; r++) {
		if (rep[r])
			continue;
		cnt = 0;
		rep[r] = r, qu[cnt++] = r;
		while (cnt) {
			int u = qu[--cnt], h, h_, tmp;

			l = 0;
			while (u > 0)
				aa[l++] = (u - 1) % 4, u = (u - 1) / 4;
			for (h = 0, h_ = l - 1; h < h_; h++, h_--)
				tmp = aa[h], aa[h] = aa[h_], aa[h_] = tmp;
			for (h = 0; h < l; h++)
				bb[h] = (h == 0 ? 0 : bb[h - 1]) * 4 + (aa[h] + 1);
			for (h = l - 1; h >= 0; h--)
				cc[h] = (h == 0 ? 0 : cc[h + 1]) + (aa[h] + 1) * pp4[l - 1 - h];
			for (h = 0; h + 1 < l; h++)
				if ((aa[h + 1] - aa[h] + 4) % 4 == 2) {
					int a = (aa[h] + 1) % 4;
					int v = ((h < 2 ? 0 : bb[h - 2]) * 4 + (a + 1)) * pp4[l - 2 - h] + (h + 2 == l ? 0 : cc[h + 2]);

					if (!rep[v])
						rep[v] = r, qu[cnt++] = v;
				}
			if (l < L)
				for (h = 0; h < l; h++) {
					int a = (aa[h] + 3) % 4, b = (aa[h] + 1) % 4;
					int v = (((h == 0 ? 0 : bb[h - 1]) * 4 + (a + 1)) * 4 + (b + 1)) * pp4[l - 1 - h] + (h + 1 == l ? 0 : cc[h + 1]);

					if (!rep[v])
						rep[v] = r, qu[cnt++] = v;
				}
		}
	}
}

int main() {
	static int rep_[N];
	static char ans[N][N + 1];
	int n, i, j;

	init();
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		static char cc[L_ + 1];
		int l, h, u;

		scanf("%s", cc), l = strlen(cc);
		u = 0;
		for (h = 0; h < l; h++)
			u = u * 4 + (strchr(acgt, cc[h]) - acgt + 1);
		rep_[i] = rep[u];
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ans[i][j] = rep_[i] == rep_[j] ? '1' : '0';
	for (i = 0; i < n; i++)
		printf("%s\n", ans[i]);
	return 0;
}

Compilation message (stderr)

gta.c: In function 'main':
gta.c:66:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
gta.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%s", cc), l = strlen(cc);
      |   ^~~~~~~~~~~~~~~
gta.c: In function 'init':
gta.c:43:93: warning: array subscript 3 is above array bounds of 'int[2]' [-Warray-bounds]
   43 |      int v = ((h < 2 ? 0 : bb[h - 2]) * 4 + (a + 1)) * pp4[l - 2 - h] + (h + 2 == l ? 0 : cc[h + 2]);
      |                                                                                           ~~^~~~~~~
gta.c:14:27: note: while referencing 'cc'
   14 |  static int aa[L], bb[L], cc[L], pp4[L + 1], qu[N];
      |                           ^~
gta.c:39:29: warning: array subscript 2 is above array bounds of 'int[2]' [-Warray-bounds]
   39 |     cc[h] = (h == 0 ? 0 : cc[h + 1]) + (aa[h] + 1) * pp4[l - 1 - h];
      |                           ~~^~~~~~~
gta.c:14:27: note: while referencing 'cc'
   14 |  static int aa[L], bb[L], cc[L], pp4[L + 1], qu[N];
      |                           ^~

• Subtask 1: 0 / 100