Submission #113462

#	Time	Username	Problem	Language	Result	Execution time	Memory
113462		tincamatei	Broken Device (JOI17_broken_device)	C++14	0 / 100	7 ms	1024 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 150;

bool broken[MAX_N];
int perm[MAX_N];

void makePseudoPerm() {
	srand(269696969);
	for(int i = 0; i < MAX_N; ++i)
		perm[i] = i;
	
	random_shuffle(perm, perm + MAX_N);
}

void Anna(int N, long long X, int k, int P[]) {
	makePseudoPerm();
	for(int i = 0; i < k; ++i)
		broken[P[i]] = true;
	for(int i = 0; i < 62; ++i)
		Set(perm[i], ((1LL << i) & X) > 0);

	for(int i = 62; i < N - 62 - 1; ++i) {
		bool ok = true;
		if(!broken[perm[i]]) {
			for(int j = 0; j < 62; ++j)
				if(broken[perm[j]] && broken[perm[i + j + 1]])
					ok = false;
		
			if(ok) {
				Set(perm[i], true);
				for(int j = 0; j < 62; ++j)
					Set(perm[i + j + 1], ((1LL << j) & X) > 0);
				for(int j = i + 63; j < N; ++j)
					Set(perm[j], false);
				return;
			} else
				Set(perm[i], false);
		}
	}

	assert(false); // This should not happen
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 150;

static int perm[MAX_N];

static void makePseudoPerm() {
	srand(269696969);
	for(int i = 0; i < MAX_N; ++i)
		perm[i] = i;
	
	random_shuffle(perm, perm + MAX_N);
}

long long Bruno(int N, int A[]) {
	makePseudoPerm();
	long long X = 0LL;

	for(int i = 0; i < 62; ++i)
		X = X | ((long long)A[perm[i]] << i);
	int i = 62;
	while(A[perm[i]] != 1)
		++i;
	i++;
	for(int j = 0; j < 62; ++j)
		X = X | ((long long)A[perm[i + j]] << j);

	return X;
}

• Subtask 1: 0 / 100