oj.uz

Submission #492130

# Submission time Handle Problem Language Result Execution time Memory
492130 2021-12-05T14:59:07 Z keta_tsimakuridze "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 303 ms 7528 KB 
#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

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

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 7436 KB Ok
2 Correct 109 ms 3728 KB Ok
3 Correct 2 ms 204 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 6 ms 460 KB Ok
3 Correct 115 ms 3740 KB Ok
4 Correct 59 ms 2012 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 2 ms 332 KB Ok
7 Correct 35 ms 1160 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 7360 KB Ok
2 Correct 303 ms 7388 KB Ok
3 Correct 221 ms 7476 KB Ok
4 Correct 109 ms 3692 KB Ok
5 Correct 122 ms 3776 KB Ok
6 Correct 47 ms 1976 KB Ok
7 Correct 48 ms 2052 KB Ok
8 Correct 25 ms 1168 KB Ok
9 Correct 25 ms 1096 KB Ok
10 Correct 11 ms 768 KB Ok
11 Correct 1 ms 204 KB Ok
12 Correct 1 ms 292 KB Ok
13 Correct 0 ms 204 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 7436 KB Ok
2 Correct 109 ms 3728 KB Ok
3 Correct 2 ms 204 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 6 ms 460 KB Ok
8 Correct 115 ms 3740 KB Ok
9 Correct 59 ms 2012 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 2 ms 332 KB Ok
12 Correct 35 ms 1160 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 223 ms 7360 KB Ok
15 Correct 303 ms 7388 KB Ok
16 Correct 221 ms 7476 KB Ok
17 Correct 109 ms 3692 KB Ok
18 Correct 122 ms 3776 KB Ok
19 Correct 47 ms 1976 KB Ok
20 Correct 48 ms 2052 KB Ok
21 Correct 25 ms 1168 KB Ok
22 Correct 25 ms 1096 KB Ok
23 Correct 11 ms 768 KB Ok
24 Correct 1 ms 204 KB Ok
25 Correct 1 ms 292 KB Ok
26 Correct 0 ms 204 KB Ok
27 Correct 224 ms 7500 KB Ok
28 Correct 100 ms 3724 KB Ok
29 Correct 232 ms 7472 KB Ok
30 Correct 11 ms 716 KB Ok
31 Correct 2 ms 320 KB Ok
32 Correct 7 ms 460 KB Ok
33 Correct 24 ms 1148 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 1 ms 204 KB Ok
36 Correct 1 ms 204 KB Ok
37 Correct 0 ms 204 KB Ok
38 Correct 107 ms 3808 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3784 KB Ok
2 Correct 215 ms 7468 KB Ok
3 Correct 234 ms 7528 KB Ok
4 Correct 11 ms 716 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 24 ms 1076 KB Ok
7 Correct 218 ms 7440 KB Ok
8 Correct 1 ms 204 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 51 ms 1980 KB Ok
12 Correct 118 ms 3816 KB Ok