oj.uz

Submission #206684

# Submission time Handle Problem Language Result Execution time Memory
206684 2020-03-04T12:57:27 Z bash "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 97 ms 44636 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);
			}
		}
	}
	vec.pop_back();
	used[x] = 0;
}
 
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::__cxx11::string&)':
lyuboyn.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) {
                  ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int com(std::__cxx11::string, std::__cxx11::string)':
lyuboyn.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                  ~~^~~~~~~~~~
lyuboyn.cpp: At global scope:
lyuboyn.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 44396 KB Ok
2 Correct 46 ms 22380 KB Ok
3 Correct 5 ms 504 KB Ok
4 Correct 5 ms 376 KB Ok
5 Correct 5 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Ok
2 Correct 7 ms 1656 KB Ok
3 Correct 45 ms 22380 KB Ok
4 Correct 25 ms 11380 KB Ok
5 Correct 5 ms 376 KB Ok
6 Correct 5 ms 632 KB Ok
7 Correct 13 ms 5884 KB Ok
8 Correct 5 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 44636 KB Ok
2 Correct 90 ms 44392 KB Ok
3 Correct 87 ms 44524 KB Ok
4 Correct 46 ms 22516 KB Ok
5 Correct 51 ms 22384 KB Ok
6 Correct 26 ms 11380 KB Ok
7 Correct 25 ms 11380 KB Ok
8 Correct 14 ms 5880 KB Ok
9 Correct 16 ms 6136 KB Ok
10 Correct 9 ms 3064 KB Ok
11 Correct 5 ms 504 KB Ok
12 Correct 5 ms 504 KB Ok
13 Correct 5 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 44396 KB Ok
2 Correct 46 ms 22380 KB Ok
3 Correct 5 ms 504 KB Ok
4 Correct 5 ms 376 KB Ok
5 Correct 5 ms 376 KB Ok
6 Correct 5 ms 376 KB Ok
7 Correct 7 ms 1656 KB Ok
8 Correct 45 ms 22380 KB Ok
9 Correct 25 ms 11380 KB Ok
10 Correct 5 ms 376 KB Ok
11 Correct 5 ms 632 KB Ok
12 Correct 13 ms 5884 KB Ok
13 Correct 5 ms 376 KB Ok
14 Correct 91 ms 44636 KB Ok
15 Correct 90 ms 44392 KB Ok
16 Correct 87 ms 44524 KB Ok
17 Correct 46 ms 22516 KB Ok
18 Correct 51 ms 22384 KB Ok
19 Correct 26 ms 11380 KB Ok
20 Correct 25 ms 11380 KB Ok
21 Correct 14 ms 5880 KB Ok
22 Correct 16 ms 6136 KB Ok
23 Correct 9 ms 3064 KB Ok
24 Correct 5 ms 504 KB Ok
25 Correct 5 ms 504 KB Ok
26 Correct 5 ms 376 KB Ok
27 Correct 89 ms 44484 KB Ok
28 Correct 45 ms 22252 KB Ok
29 Correct 88 ms 44524 KB Ok
30 Correct 9 ms 3064 KB Ok
31 Correct 5 ms 504 KB Ok
32 Correct 7 ms 1656 KB Ok
33 Correct 14 ms 5880 KB Ok
34 Correct 5 ms 376 KB Ok
35 Correct 5 ms 376 KB Ok
36 Correct 5 ms 376 KB Ok
37 Correct 5 ms 256 KB Ok
38 Correct 47 ms 22384 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 22260 KB Ok
2 Correct 97 ms 44528 KB Ok
3 Correct 89 ms 44524 KB Ok
4 Correct 9 ms 3064 KB Ok
5 Correct 5 ms 376 KB Ok
6 Correct 14 ms 5880 KB Ok
7 Correct 86 ms 44392 KB Ok
8 Correct 6 ms 504 KB Ok
9 Correct 5 ms 376 KB Ok
10 Correct 5 ms 508 KB Ok
11 Correct 26 ms 11380 KB Ok
12 Correct 45 ms 22256 KB Ok