oj.uz

Submission #762650

# Submission time Handle Problem Language Result Execution time Memory
762650 2023-06-21T15:26:09 Z NK_ "The Lyuboyn" code (IZhO19_lyuboyn) C++17
8 / 100
 117 ms 36112 KB 
// 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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 0 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 36112 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 25960 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 36112 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 15436 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -