Submission #874831

#	Time	Username	Problem	Language	Result	Execution time	Memory
874831		rainboy	Data Transfer (IOI19_transfer)	C++17	100 / 100	74 ms	2760 KiB

transfer

#include "transfer.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

vi get_attachment(vi aa) {
	int n = aa.size(), l = 0;
	while (1 << l <= n)
		l++;
	vi xx(l + 1, 0);
	int x = 0;
	for (int i = 0; i < n; i++)
		if (aa[i] == 1)
			x ^= i + 1;
	int k = 0;
	for (int h = 0; h < l; h++)
		if ((x & 1 << h) != 0)
			xx[h] = 1, k++;
	if (k % 2 != 0)
		xx[l] = 1;
	return xx;
}

vi retrieve(vi bb) {
	int m = bb.size(), n = 0, l = 0;
	while (1) {
		n++;
		while (1 << l <= n)
			l++;
		if (m == n + l + 1)
			break;
	}
	int x = 0, k = 0;
	for (int h = 0; h <= l; h++)
		if (bb[n + h] == 1) {
			if (h < l)
				x |= 1 << h;
			k++;
		}
	bb.resize(n);
	if (k % 2 == 0) {
		for (int i = 0; i < n; i++)
			if (bb[i] == 1)
				x ^= i + 1;
		if (x != 0)
			bb[x - 1] ^= 1;
	}
	return bb;
}

• Subtask 1: 60 / 60
• Subtask 2: 40 / 40