oj.uz

Submission #492127

# Submission time Handle Problem Language Result Execution time Memory
492127 2021-12-05T14:53:41 Z keta_tsimakuridze "The Lyuboyn" code (IZhO19_lyuboyn) C++14
34 / 100
 231 ms 7532 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;
}
main(){
	cin >> n >> k >> t;
	if(k % 2 == 0 || n == k) {
		cout << -1;
		exit(0);
	}
	vector<int> a = solve(n, k);
	cout << (1 << n) << "\n";	
	for(int i = 0; i < a.size(); i++) {
		assert(!i || __builtin_popcount(a[i] ^ a[i - 1]) == k);
		for(int j = n - 1; j >= 0; j--) {
			if((1 << j) & a[i]) cout << 1;
			else cout << 0;
		}
		cout << "\n";
	
	}
}

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:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:59:19: 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]
   59 |  for(int i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB First number in answer is not x 1 0

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 7532 KB Ok
2 Correct 107 ms 3756 KB Ok
3 Correct 1 ms 320 KB Ok
4 Correct 0 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 99 ms 3812 KB Ok
4 Correct 50 ms 2092 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 3 ms 332 KB Ok
7 Correct 27 ms 1172 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 7468 KB First number in answer is not x 44202 0
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 7532 KB Ok
2 Correct 107 ms 3756 KB Ok
3 Correct 1 ms 320 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 6 ms 460 KB Ok
8 Correct 99 ms 3812 KB Ok
9 Correct 50 ms 2092 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 3 ms 332 KB Ok
12 Correct 27 ms 1172 KB Ok
13 Correct 1 ms 204 KB Ok
14 Incorrect 214 ms 7468 KB First number in answer is not x 44202 0
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 3744 KB First number in answer is not x 92826 0
2 Halted 0 ms 0 KB -