/* upsolve after reading solution */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define L 7
#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);
| ^~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(assert.o): in function `__assert_fail_base':
(.text+0x114): relocation truncated to fit: R_X86_64_PC32 against symbol `__abort_msg' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(abort.o)
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(loadmsgcat.o): in function `_nl_load_domain':
(.text+0x3c): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x5a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x61): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x67): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x73): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x48a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4a1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4ac): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4c2): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x510): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
