oj.uz

Submission #948206

# Submission time Handle Problem Language Result Execution time Memory
948206 2024-03-17T21:42:54 Z rainboy Walk (POI13_spa) C
75 / 100
 5000 ms 262144 KB 
/* https://oi.edu.pl/static/attachment/20140306/oi20.pdf */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define M	3000000
#define N_	5000001
#define L	60
#define MD	0x7fffffff
 
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
 
int X = 123454321;
 
int k;
 
long long parse() {
	static char cc[L + 1];
	int h;
	long long x;
 
	scanf("%s", cc);
	x = 0;
	for (h = 0; h < k; h++)
		if (cc[h] == '1')
			x |= 1LL << h;
	return x;
}
 
long long *ek[M]; int eo[M];
char *ev[M];

int hash(long long k) {
	int kl = k / MD, kr = k % MD;

	return ((long long) kl * X % MD + kr) * X % MD % M;
}

int ht_add(long long k, int v) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k) {
			if (ev[h][o] == (v ^ 1)) {
				printf("TAK\n");
				exit(0);
			}
			return 0;
		}
	o = eo[h]++;
	if (o == 0) {
		ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
		ev[h] = (char *) malloc(2 * sizeof *ev[h]);
	} else if (o >= 2 && (o & o - 1) == 0) {
		ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
		ev[h] = (char *) realloc(ev[h], o * 2 * sizeof *ev[h]);
	}
	ek[h][o] = k, ev[h][o] = v;
	return 1;
}

int bfs(long long s, int cnt_, int v) {
	static long long qu[N_];
	int cnt, g, h;
	long long b, b_;

	cnt = 0;
	ht_add(s, v), qu[cnt++] = s;
	for (g = 0; g < cnt; g++) {
		b = qu[g];
		for (h = 0; h < k; h++) {
			b_ = b ^ 1LL << h;
			if (ht_add(b_, v)) {
				qu[cnt++] = b_;
				if (cnt == cnt_)
					return 1;
			}
		}
	}
	return 0;
}

int main() {
	int n, i;
	long long s, t;
 
	scanf("%d%d", &k, &n), s = parse(), t = parse();
	if (s == t) {
		printf("TAK\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		ht_add(parse(), -1);
	ht_add(s, 0), ht_add(t, 1);
	printf(bfs(s, n * k + 1, 0) && bfs(t, n * k + 1, 1) ? "TAK\n" : "NIE\n");
	return 0;
}

Compilation message

spa.c: In function 'ht_add':
spa.c:55:30: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   55 |  } else if (o >= 2 && (o & o - 1) == 0) {
      |                            ~~^~~
spa.c: In function 'parse':
spa.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%s", cc);
      |  ^~~~~~~~~~~~~~~
spa.c: In function 'main':
spa.c:88:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d", &k, &n), s = parse(), t = parse();
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 53848 KB Output is correct
2 Correct 12 ms 56100 KB Output is correct
3 Correct 13 ms 57944 KB Output is correct
4 Correct 18 ms 61812 KB Output is correct
5 Correct 26 ms 61780 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 8536 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16872 KB Output is correct
10 Correct 2 ms 16728 KB Output is correct
11 Correct 112 ms 73464 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 75192 KB Output is correct
2 Correct 293 ms 77732 KB Output is correct
3 Execution timed out 5063 ms 198528 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 54108 KB Output is correct
2 Correct 56 ms 69912 KB Output is correct
3 Correct 99 ms 78040 KB Output is correct
4 Correct 22 ms 63556 KB Output is correct
5 Correct 23 ms 63576 KB Output is correct
6 Correct 9 ms 56412 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 58460 KB Output is correct
2 Correct 8 ms 53080 KB Output is correct
3 Correct 65 ms 72536 KB Output is correct
4 Correct 96 ms 79092 KB Output is correct
5 Correct 98 ms 79288 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 68672 KB Output is correct
2 Correct 3009 ms 258760 KB Output is correct
3 Runtime error 2957 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 67144 KB Output is correct
2 Correct 527 ms 134280 KB Output is correct
3 Correct 1036 ms 178160 KB Output is correct
4 Correct 1811 ms 222116 KB Output is correct
5 Correct 1725 ms 221572 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 73488 KB Output is correct
2 Correct 4738 ms 256012 KB Output is correct
3 Correct 4585 ms 256524 KB Output is correct
4 Correct 2308 ms 200472 KB Output is correct
5 Correct 81 ms 67924 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 72936 KB Output is correct
2 Correct 66 ms 66164 KB Output is correct
3 Correct 1331 ms 172216 KB Output is correct
4 Correct 79 ms 68948 KB Output is correct
5 Correct 3037 ms 225220 KB Output is correct