Submission #762650

#	Time	Username	Problem	Language	Result	Execution time	Memory
762650		NK_	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	8 / 100	117 ms	36112 KiB

lyuboyn

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
using str = string;

template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	bool CHECK = 0;
	int N, K, T; cin >> N >> K >> T;
	str S; cin >> S;

	if (K % 2 == 0) {
		cout << -1 << nl;
		return 0;
	}

	auto BIN = [&](int x, int len) {
		str s;
		for(int t = 0; t < len; t++){ s += char('0' + x % 2); x /= 2; }
		reverse(begin(s), end(s));
		return s;
	};

	auto DEC = [&](str s) {
		int x = 0;
		for(auto& c : s) x = 2 * x + (c == '1');
		return x;
	};

	auto XOR = [&](str a, str b) {
		str c;
		for(int i = 0; i < N; i++) c += char('0' + (a[i] != b[i]));
		return c;
	};

	int M = N - K;

	int SIZ = (1 << max(M, K));
	V<str> A(SIZ);

	for(int i = 0; i < SIZ / 2; i++) {
		int x = i % (1 << M);
		int y = i % (1 << (K - 1));

		A[2 * i] = BIN(x ^ (x >> 1), M) + BIN(y ^ (y >> 1), K);
		A[2 * i + 1] = BIN(x ^ (x >> 1), M) + BIN(y ^ (y >> 1) ^ ((1 << K) - 1), K);
	}

	int n = (1 << N);

	str CUR = S, DIF = str(M - 1, '0') + "10" + str(K - 1, '1');
	cout << n << nl;
	V<str> ans;
	for(int t = 0; t < (n / SIZ); t++) {
		for(auto x : A) {
			cout << XOR(CUR, x) << nl;
			ans.push_back(XOR(CUR, x));
		}
		CUR = XOR(XOR(CUR, A.back()), DIF);
	}
		

	auto dif = [&](str a, str b) {
		str c = XOR(a, b);
		return count(begin(c), end(c), '1');
	};

	if (CHECK) {
		for(int i = 0; i < n; i++) if (dif(ans[i], ans[(i+1)%n]) != K) assert(false);
	}	

    return 0;
}

Compilation message (stderr)

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:30:7: warning: variable 'DEC' set but not used [-Wunused-but-set-variable]
   30 |  auto DEC = [&](str s) {
      |       ^~~

• Subtask 1: 0 / 0
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 31
• Subtask 8: 0 / 17