oj.uz

Submission #173747

# Submission time Handle Problem Language Result Execution time Memory
173747 2020-01-05T09:34:16 Z Just_Solve_The_Problem "The Lyuboyn" code (IZhO19_lyuboyn) C++11
100 / 100
 112 ms 44716 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 2 ms 376 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 44464 KB Ok
2 Correct 53 ms 22384 KB Ok
3 Correct 2 ms 504 KB Ok
4 Correct 2 ms 252 KB Ok
5 Correct 2 ms 376 KB Ok

Subtask #5
15.0 / 15.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 44540 KB Ok
2 Correct 105 ms 44524 KB Ok
3 Correct 107 ms 44484 KB Ok
4 Correct 53 ms 22396 KB Ok
5 Correct 53 ms 22384 KB Ok
6 Correct 27 ms 11380 KB Ok
7 Correct 28 ms 11412 KB Ok
8 Correct 13 ms 5880 KB Ok
9 Correct 14 ms 6008 KB Ok
10 Correct 8 ms 3064 KB Ok
11 Correct 2 ms 504 KB Ok
12 Correct 2 ms 504 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 44464 KB Ok
2 Correct 53 ms 22384 KB Ok
3 Correct 2 ms 504 KB Ok
4 Correct 2 ms 252 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 5 ms 1656 KB Ok
8 Correct 53 ms 22380 KB Ok
9 Correct 27 ms 11380 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 632 KB Ok
12 Correct 13 ms 5880 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 106 ms 44540 KB Ok
15 Correct 105 ms 44524 KB Ok
16 Correct 107 ms 44484 KB Ok
17 Correct 53 ms 22396 KB Ok
18 Correct 53 ms 22384 KB Ok
19 Correct 27 ms 11380 KB Ok
20 Correct 28 ms 11412 KB Ok
21 Correct 13 ms 5880 KB Ok
22 Correct 14 ms 6008 KB Ok
23 Correct 8 ms 3064 KB Ok
24 Correct 2 ms 504 KB Ok
25 Correct 2 ms 504 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 107 ms 44444 KB Ok
28 Correct 61 ms 22484 KB Ok
29 Correct 110 ms 44716 KB Ok
30 Correct 8 ms 3064 KB Ok
31 Correct 3 ms 504 KB Ok
32 Correct 5 ms 1656 KB Ok
33 Correct 13 ms 5880 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 53 ms 22256 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 22384 KB Ok
2 Correct 108 ms 44488 KB Ok
3 Correct 108 ms 44640 KB Ok
4 Correct 7 ms 3064 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 15 ms 5880 KB Ok
7 Correct 106 ms 44524 KB Ok
8 Correct 2 ms 532 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 3 ms 504 KB Ok
11 Correct 30 ms 11380 KB Ok
12 Correct 53 ms 22268 KB Ok