oj.uz

Submission #492129

# Submission time Handle Problem Language Result Execution time Memory
492129 2021-12-05T14:58:18 Z keta_tsimakuridze "The Lyuboyn" code (IZhO19_lyuboyn) C++14
3 / 100
 441 ms 12408 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 < a.size(); 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(){
      | ^~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:80:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i + 1 < a.size(); i++) {
      |                 ~~~~~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB More lines are printed!

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 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 0 ms 204 KB Ok
8 Correct 0 ms 204 KB Ok

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 12408 KB More lines are printed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB More lines are printed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 10492 KB More lines are printed!
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 12408 KB More lines are printed!
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 5552 KB More lines are printed!
2 Halted 0 ms 0 KB -