| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 485407 |
2021-11-07T16:30:17 Z |
rainboy |
GTA (COI14_gta) |
C |
|
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);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
