Submission #837253

#	Time	Username	Problem	Language	Result	Execution time	Memory
837253		TranGiaHuy1508	Broken Device (JOI17_broken_device)	C++17	85 / 100	35 ms	2512 KiB

Anna

#include <bits/stdc++.h>
using namespace std;

#include "Annalib.h"

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

namespace {
	ll SEED = 123456790;
	mt19937_64 rng(SEED);

	bool init = false;
	vector<vvi> mapping;

	void generate(){
		if (init) return;
		init = true;

		vvi M = {{1, 6}, {2, 5}, {3, 4}, {7}};
		for (int i = 0; i < 50; i++){
			vvi _M = M;
			shuffle(_M.begin(), _M.end(), rng);
			mapping.push_back(_M);
		}
	}
}

void Anna(int N, ll X, int K, int P[]){
	generate();

	vector<int> broken(N, 0);
	for (int i = 0; i < K; i++) broken[P[i]] = 1;

	// cout << "Anna: ";
	for (int i = 0; i < N; i += 3){
		vector<int> S(3);
		iota(S.begin(), S.end(), i);

		int valid = 7;
		for (int j = 0; j < 3; j++){
			if (broken[S[j]]) valid ^= (1 << j);
		}

		int ed = X & 3;
		int R = 0;
		for (auto mask: mapping[i/3][ed]){
			if ((valid & mask) == mask) R = mask;
		}

		for (int j = 0; j < 3; j++){
			Set(S[j], (R >> j) & 1);
			// cout << ((R >> j) & 1);
		}

		if (R > 0) X >>= 2;
	}
	// cout << "\n";
}

Bruno

#include <bits/stdc++.h>
using namespace std;

#include "Brunolib.h"

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

namespace {
	ll SEED = 123456790;
	mt19937_64 rng(SEED);

	bool init = false;
	vector<vvi> mapping;

	void generate(){
		if (init) return;
		init = true;

		vvi M = {{1, 6}, {2, 5}, {3, 4}, {7}};
		for (int i = 0; i < 50; i++){
			vvi _M = M;
			shuffle(_M.begin(), _M.end(), rng);
			mapping.push_back(_M);
		}
	}
}

ll Bruno(int N, int A[]){
	generate();

	ll answer = 0;
	for (int i = N-3; i >= 0; i -= 3){
		vector<int> S(3);
		iota(S.begin(), S.end(), i);

		int repr = 0;
		for (int j = 0; j < 3; j++){
			repr += (A[S[j]] << j);
		}

		int value = -1;
		for (int j = 0; j < 4; j++){
			for (auto k: mapping[i/3][j]){
				if (repr == k) value = j;
			}
		}

		if (value >= 0) answer = (answer << 2) + value;
	}

	// cout << "Bruno: " << answer << "\n";
	return answer;
}

• Subtask 1: 85 / 100