oj.uz

Submission #683547

# Submission time Handle Problem Language Result Execution time Memory
683547 2023-01-18T17:11:46 Z rainboy Broken Device (JOI17_broken_device) C
100 / 100
 87 ms 2636 KB 
#include "Annalib.h"
#include <string.h>

static const int N = 150, L = 60;

static void add(long long *bb, long long b) {
	for (int l = 0; l < L; l++)
		if ((b & 1LL << l) != 0) {
			if ((bb[l] & 1LL << l) != 0)
				b ^= bb[l];
			else {
				bb[l] = b;
				return;
			}
		}
}

static int in(long long *bb, long long b) {
	for (int l = 0; l < L; l++)
		if ((b & 1LL << l) != 0) {
			if ((bb[l] & 1LL << l) != 0)
				b ^= bb[l];
			else
				return 0;
		}
	return 1;
}

void Anna(int n, long long x, int k, int ii[]) {
	long long xx[N];
	unsigned long long X = 1427309572638513469;
	for (int i = 0; i < N; i++)
		xx[i] = ((X *= 3) >> 1) % (1LL << 60);
	char broken[N];
	memset(broken, 0, N * sizeof *broken);
	for (int h = 0; h < k; h++)
		broken[ii[h]] = 1;
	long long bb[N + 1][L];
	memset(bb[N], 0, L * sizeof *bb[N]);
	for (int i = N - 1; i >= 0; i--) {
		memcpy(bb[i], bb[i + 1], L * sizeof *bb[i + 1]);
		if (!broken[i])
			add(bb[i], xx[i]);
	}
	for (int i = 0; i < N; i++)
		if (!broken[i] && in(bb[i + 1], x ^ xx[i]))
			Set(i, 1), x ^= xx[i];
		else
			Set(i, 0);
}
#include "Brunolib.h"

static const int N = 150;

long long Bruno(int n, int aa[]) {
	long long xx[N];
	unsigned long long X = 1427309572638513469;
	for (int i = 0; i < N; i++)
		xx[i] = ((X *= 3) >> 1) % (1LL << 60);
	long long x = 0;
	for (int i = 0; i < N; i++)
		if (aa[i])
			x ^= xx[i];
	return x;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2492 KB Output is correct - L* = 40
2 Correct 85 ms 2532 KB Output is correct - L* = 40
3 Correct 82 ms 2620 KB Output is correct - L* = 40
4 Correct 79 ms 2548 KB Output is correct - L* = 40
5 Correct 87 ms 2544 KB Output is correct - L* = 40
6 Correct 80 ms 2552 KB Output is correct - L* = 40
7 Correct 79 ms 2540 KB Output is correct - L* = 40
8 Correct 81 ms 2480 KB Output is correct - L* = 40
9 Correct 79 ms 2568 KB Output is correct - L* = 40
10 Correct 78 ms 2556 KB Output is correct - L* = 40
11 Correct 80 ms 2560 KB Output is correct - L* = 40
12 Correct 80 ms 2600 KB Output is correct - L* = 40
13 Correct 80 ms 2504 KB Output is correct - L* = 40
14 Correct 78 ms 2616 KB Output is correct - L* = 40
15 Correct 79 ms 2636 KB Output is correct - L* = 40
16 Correct 80 ms 2512 KB Output is correct - L* = 40
17 Correct 79 ms 2572 KB Output is correct - L* = 40
18 Correct 79 ms 2620 KB Output is correct - L* = 40
19 Correct 81 ms 2612 KB Output is correct - L* = 40
20 Correct 80 ms 2520 KB Output is correct - L* = 40
21 Correct 81 ms 2596 KB Output is correct - L* = 40
22 Correct 80 ms 2460 KB Output is correct - L* = 40
23 Correct 79 ms 2524 KB Output is correct - L* = 40
24 Correct 83 ms 2568 KB Output is correct - L* = 40
25 Correct 79 ms 2472 KB Output is correct - L* = 40
26 Correct 81 ms 2616 KB Output is correct - L* = 40
27 Correct 81 ms 2628 KB Output is correct - L* = 40
28 Correct 78 ms 2484 KB Output is correct - L* = 40
29 Correct 82 ms 2580 KB Output is correct - L* = 40
30 Correct 77 ms 2524 KB Output is correct - L* = 40
31 Correct 79 ms 2544 KB Output is correct - L* = 40
32 Correct 79 ms 2544 KB Output is correct - L* = 40
33 Correct 80 ms 2580 KB Output is correct - L* = 40
34 Correct 79 ms 2472 KB Output is correct - L* = 40
35 Correct 79 ms 2564 KB Output is correct - L* = 40
36 Correct 80 ms 2548 KB Output is correct - L* = 40
37 Correct 78 ms 2612 KB Output is correct - L* = 40
38 Correct 80 ms 2480 KB Output is correct - L* = 40
39 Correct 79 ms 2572 KB Output is correct - L* = 40
40 Correct 82 ms 2536 KB Output is correct - L* = 40