oj.uz

Submission #344894

# Submission time Handle Problem Language Result Execution time Memory
344894 2021-01-06T17:20:57 Z bash "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 111 ms 48864 KB 
#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;          
 
int n, k, t;
vector <int> tran;
 
int val(string &s) {
	int res = 0;
	for (int i = 0; i < s.size(); i++) {
		res += ((s[i] - '0') << i);
	}
	return res;
}
 
string rev(int x) {
	string res;
	for (int i = 0; i < n; i++) {
		res += (x % 2 + '0');
		x /= 2;
	}
	return res;
}
 
int used[1 << 18];
int cnt = 0;
vector <int> vec;
 
int com(string a, string b) {
	int res = 0;
	for (int i = 0; i < a.size(); i++) {
		res += (a[i] != b[i]);
	}
	return res;
}
 
void go(int x) {
	used[x] = 1;
	cnt++;
	vec.push_back(x);
	if (cnt == (1 << n)) {
		if (t == 0 || (com(rev(vec[0]), rev(vec.back())) == k)) {
			cout << vec.size() << endl;
			for (int to : vec) {
				cout << rev(to) << '\n';
			}
			exit(0);
		}
	} else {
		for (int to : tran) {
			if (!used[x ^ to]) {
				go(x ^ to);
			}
		}
	}
}
 
main() {
	scanf("%d %d %d", &n, &k, &t);
	if (k % 2 == 0) {
		puts("-1");
		return 0;
	}
	for (int i = 0; i < (1 << n); i++) {
		if (__builtin_popcount(i) == k) {
			tran.push_back(i);
		}
	}
	string s; cin >> s;
	int x = val(s);
	go(x);
}

Compilation message

lyuboyn.cpp: In function 'int val(std::string&)':
lyuboyn.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int com(std::string, std::string)':
lyuboyn.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
lyuboyn.cpp: At global scope:
lyuboyn.cpp:60:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main() {
      |      ^
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d %d %d", &n, &k, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 48520 KB Ok
2 Correct 54 ms 24348 KB Ok
3 Correct 1 ms 492 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 3 ms 1772 KB Ok
3 Correct 48 ms 24420 KB Ok
4 Correct 27 ms 12392 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 748 KB Ok
7 Correct 11 ms 6380 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 48752 KB Ok
2 Correct 103 ms 48644 KB Ok
3 Correct 103 ms 48736 KB Ok
4 Correct 50 ms 24548 KB Ok
5 Correct 50 ms 24420 KB Ok
6 Correct 25 ms 12392 KB Ok
7 Correct 31 ms 12392 KB Ok
8 Correct 14 ms 6380 KB Ok
9 Correct 12 ms 6380 KB Ok
10 Correct 6 ms 3308 KB Ok
11 Correct 1 ms 492 KB Ok
12 Correct 1 ms 492 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 48520 KB Ok
2 Correct 54 ms 24348 KB Ok
3 Correct 1 ms 492 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 3 ms 1772 KB Ok
8 Correct 48 ms 24420 KB Ok
9 Correct 27 ms 12392 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 1 ms 748 KB Ok
12 Correct 11 ms 6380 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 101 ms 48752 KB Ok
15 Correct 103 ms 48644 KB Ok
16 Correct 103 ms 48736 KB Ok
17 Correct 50 ms 24548 KB Ok
18 Correct 50 ms 24420 KB Ok
19 Correct 25 ms 12392 KB Ok
20 Correct 31 ms 12392 KB Ok
21 Correct 14 ms 6380 KB Ok
22 Correct 12 ms 6380 KB Ok
23 Correct 6 ms 3308 KB Ok
24 Correct 1 ms 492 KB Ok
25 Correct 1 ms 492 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 101 ms 48480 KB Ok
28 Correct 50 ms 24420 KB Ok
29 Correct 103 ms 48736 KB Ok
30 Correct 6 ms 3308 KB Ok
31 Correct 1 ms 492 KB Ok
32 Correct 3 ms 1772 KB Ok
33 Correct 11 ms 6380 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 51 ms 24420 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 24420 KB Ok
2 Correct 111 ms 48480 KB Ok
3 Correct 104 ms 48864 KB Ok
4 Correct 6 ms 3308 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 12 ms 6380 KB Ok
7 Correct 100 ms 48644 KB Ok
8 Correct 1 ms 492 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 492 KB Ok
11 Correct 25 ms 12392 KB Ok
12 Correct 51 ms 24676 KB Ok