Submission #715720

#	Time	Username	Problem	Language	Result	Execution time	Memory
715720		valerikk	Broken Device (JOI17_broken_device)	C++17	85 / 100	62 ms	2720 KiB

Anna

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

using namespace std;

void Anna( int N, long long X, int K, int P[] ){
	mt19937 rnd(239);
	vector<int> ord(N);
	iota(ord.begin(), ord.end(), 0);
	shuffle(ord.begin(), ord.end(), rnd);
	vector<int> bad(N, 0);
	for (int i = 0; i < K; ++i) {
		bad[P[i]] = 1;
	}
	vector<int> a(N, 0);
	for (int i = 0; i + 1 < N; i += 2) {
		if (!bad[ord[i]] && !bad[ord[i + 1]]) {
			if (X % 3 == 0) {
				a[ord[i]] = 1;
			}
			if (X % 3 == 1) {
				a[ord[i + 1]] = 1;
			}
			if (X % 3 == 2) {
				a[ord[i]] = a[ord[i + 1]] = 1;
			}
			X /= 3;
		}
	}
	for (int i = 0; i < N; ++i) {
		Set(i, a[i]);
	}
}

Bruno

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

using namespace std;

long long Bruno( int N, int A[] ){
	mt19937 rnd(239);
	vector<int> ord(N);
	iota(ord.begin(), ord.end(), 0);
	shuffle(ord.begin(), ord.end(), rnd);
	long long X = 0;
	vector<int> digits;
	for (int i = 0; i + 1 < N; i += 2) {
		if (A[ord[i]] || A[ord[i + 1]]) {
			if (!A[ord[i + 1]]) {
				digits.push_back(0);
			}
			if (!A[ord[i]]) {
				digits.push_back(1);
			}
			if (A[ord[i]] && A[ord[i + 1]]) {
				digits.push_back(2);
			}
		}
	}
	reverse(digits.begin(), digits.end());
	for (int d : digits) {
		X = X * 3 + d;
	}
	return X;
}

• Subtask 1: 85 / 100