제출 #683547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683547		rainboy	Broken Device (JOI17_broken_device)	C11	100 / 100	87 ms	2636 KiB

Anna

#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);
}

Bruno

#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 / 100