Submission #485409

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

gta

/* upsolve after reading solution */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	10000
#define L	6
#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 + 1 == l ? 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 == 0 ? 0 : bb[h - 1]) * 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:67:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
gta.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%s", cc), l = strlen(cc);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 30 / 100