답안 #485407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485407 2021-11-07T16:30:17 Z rainboy GTA (COI14_gta) C
30 / 100
2 ms 716 KB
/* upsolve after reading solution */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	10000
#define L	5
#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

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);
      |   ^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Incorrect 0 ms 716 KB Output isn't correct
5 Incorrect 0 ms 588 KB Output isn't correct
6 Incorrect 0 ms 588 KB Output isn't correct
7 Runtime error 2 ms 332 KB Execution killed with signal 11
8 Runtime error 2 ms 332 KB Execution killed with signal 11
9 Runtime error 2 ms 332 KB Execution killed with signal 11
10 Runtime error 2 ms 332 KB Execution killed with signal 11