Submission #492130

#	Time	Username	Problem	Language	Result	Execution time	Memory
492130		keta_tsimakuridze	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	100 / 100	303 ms	7528 KiB

lyuboyn

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, n, k;
vector<int> gray(int n) {
	vector<int> a;
		if(n == 1) {
			a.push_back(0);
			a.push_back(1);
			return a;
		}
		a = gray(n - 1);
		int x = a.size();
		for(int i = x - 1; i >= 0; i--) {
			a.push_back(a[i] + (1 << (n - 1)));
		}
	return a;
}
vector<int> solve(int n, int k) {
	if(n != k + 1) {
		vector<int> a = solve(n - 1, k);
		int x = a.size(); 
		for(int i = x - 1; i >= 0; i--) a.push_back(a[i] ^ ((1 << (k - 1)) - 1) + (1 << (n - 1)));
		return a;
	}
	if(k == 1) {
		return gray(n);
	}
	vector<int> a = solve(n - 2, k - 2);
	vector<int> b = a;
	int x = a.size();

	for(int i = 0; i < x; i++) if(i % 2) b[i] += (1 << (n - 1)) + (1 << (n - 2));
	
	for(int i = x - 1; i >= 0; i--) {
		if((x - 1 - i ) % 2 == 0) b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 2)));
		else b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 1)));
	}
	for(int i = 0; i < x; i++) if(i % 2 == 0) b.push_back(a[i] + (1 << (n - 1)) + (1 << (n - 2)));
	else b.push_back(a[i]);
	for(int i = x - 1; i > -1; i--) {
		if((x - 1 - i ) % 2 == 1) b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 2)));
		else b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 1)));
	}return b;
	return b;
}
void out(int a) {
			for(int j = n - 1; j >= 0; j--) {
				if((1 << j) & a) cout << 1;
				else cout << 0;
			}
			cout << "\n";	
}
main(){
	cin >> n >> k >> t;
	if(k % 2 == 0 || n == k) {
		cout << -1;
		exit(0);
	}
	string st;
	int f = 0;
	cin >> st;
	reverse(st.begin(), st.end());
	int s = 0;
	for(int i = 0; i < n; i++) {
		s += (1 << i) * (st[i] == '1');
	}
	vector<int> a = solve(n, k);
	cout << (1 << n) << "\n";	
	for(int i = 0; i < (1 << n); i++) {
		if(a[i] == s) f = i + 1;
		if(f) {
			out(a[i]);		
		}
	}
	for(int i = 0; i + 1 < f; i++) {
		out(a[i]);
	}
}

Compilation message (stderr)

lyuboyn.cpp: In function 'std::vector<long long int> solve(long long int, long long int)':
lyuboyn.cpp:27:75: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   27 |   for(int i = x - 1; i >= 0; i--) a.push_back(a[i] ^ ((1 << (k - 1)) - 1) + (1 << (n - 1)));
      |                                                      ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
lyuboyn.cpp:40:69: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   40 |   if((x - 1 - i ) % 2 == 0) b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 2)));
      |                                                ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
lyuboyn.cpp:41:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   41 |   else b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 1)));
      |                           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
lyuboyn.cpp:46:69: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   46 |   if((x - 1 - i ) % 2 == 1) b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 2)));
      |                                                ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
lyuboyn.cpp:47:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   47 |   else b.push_back(a[i] ^ ((1 << (n - 2)) - 1) + (1 << (n - 1)));
      |                           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
lyuboyn.cpp: At global scope:
lyuboyn.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main(){
      | ^~~~

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