oj.uz

Submission #181145

# Submission time Handle Problem Language Result Execution time Memory
181145 2020-01-09T07:06:02 Z BThero "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 771 ms 23580 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define S second
#define F first
#define all(x) (x).begin(), (x).end()


using namespace std;

const bool dbg_flg = 1;
#define debug(x) if (dbg_flg) cerr << #x << ' ' << x << '\n'
#define debug_pair(x) if (dbg_flg) cerr << #x << ' ' << x.F << ' ' << x.S << '\n'
 
const int inf = 1e9 + 7;
const int MAXN = (1 << 18) + 5;

vector<int> V;

int n, k, t;

string st;

int arr[MAXN];

bool used[MAXN];

int f(int a, int b) {
	return __builtin_popcount(a ^ b);
}

string str(int x) {
	string ret;

	while (x > 0) {
		ret.pb(x % 2 + '0');
		x /= 2;
	}

	while (ret.size() < n) {
		ret.pb('0');
	}

	reverse(ret.begin(), ret.end());
	return ret;
}

void printAns() {
	cout << (1 << n) << endl;

	for (int i = 0; i < (1 << n); ++i) {
		cout << str(arr[i]) << endl;
	}

	exit(0);
}

void rec(int v) {
	if (v == (1 << n) - 1) {
		if (t == 1) {
			if (f(arr[v], arr[0]) == k) {
				printAns();				
			}			
		}
		else {
			printAns();
		}

        return;             
	}

	for (int y : V) {
		int x = (arr[v] ^ y);

		if (!used[x] && f(arr[v], x) == k) {
			used[x] = 1;
			arr[v + 1] = x;
			rec(v + 1);
			used[x] = 0;
		}
	}
}

int bin(string s) {
	reverse(all(s));
	int ret = 0;

	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '1') {
			ret += (1 << i);
		}
	}

	return ret;
}

int main() {
	
	//~ freopen(".in", "r", stdin);
	//~ freopen(".out", "w", stdout);
	
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k >> t;
	cin >> st;

	if (k % 2 == 0) {
		cout << -1 << endl;
		return 0;
	}

	for (int i = 0; i < (1 << n); ++i) {
		if (__builtin_popcount(i) == k) {
			V.pb(i);
		}
	}

	arr[0] = bin(st);
	used[bin(st)] = 1;    
	rec(0);
	return 0;
}

Compilation message

lyuboyn.cpp: In function 'std::__cxx11::string str(int)':
lyuboyn.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ret.size() < n) {
         ~~~~~~~~~~~^~~
lyuboyn.cpp: In function 'int bin(std::__cxx11::string)':
lyuboyn.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i) {
                  ~~^~~~~~~~~~

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 376 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 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 348 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 1 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 23148 KB Ok
2 Correct 373 ms 11640 KB Ok
3 Correct 4 ms 376 KB Ok
4 Correct 2 ms 376 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 25 ms 988 KB Ok
3 Correct 374 ms 11684 KB Ok
4 Correct 189 ms 5880 KB Ok
5 Correct 4 ms 376 KB Ok
6 Correct 8 ms 504 KB Ok
7 Correct 97 ms 3120 KB Ok
8 Correct 3 ms 392 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 23516 KB Ok
2 Correct 771 ms 23024 KB Ok
3 Correct 745 ms 23168 KB Ok
4 Correct 372 ms 11892 KB Ok
5 Correct 371 ms 11512 KB Ok
6 Correct 184 ms 6032 KB Ok
7 Correct 188 ms 5896 KB Ok
8 Correct 93 ms 3088 KB Ok
9 Correct 94 ms 3132 KB Ok
10 Correct 47 ms 1688 KB Ok
11 Correct 5 ms 376 KB Ok
12 Correct 5 ms 376 KB Ok
13 Correct 3 ms 428 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 23148 KB Ok
2 Correct 373 ms 11640 KB Ok
3 Correct 4 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 25 ms 988 KB Ok
8 Correct 374 ms 11684 KB Ok
9 Correct 189 ms 5880 KB Ok
10 Correct 4 ms 376 KB Ok
11 Correct 8 ms 504 KB Ok
12 Correct 97 ms 3120 KB Ok
13 Correct 3 ms 392 KB Ok
14 Correct 762 ms 23516 KB Ok
15 Correct 771 ms 23024 KB Ok
16 Correct 745 ms 23168 KB Ok
17 Correct 372 ms 11892 KB Ok
18 Correct 371 ms 11512 KB Ok
19 Correct 184 ms 6032 KB Ok
20 Correct 188 ms 5896 KB Ok
21 Correct 93 ms 3088 KB Ok
22 Correct 94 ms 3132 KB Ok
23 Correct 47 ms 1688 KB Ok
24 Correct 5 ms 376 KB Ok
25 Correct 5 ms 376 KB Ok
26 Correct 3 ms 428 KB Ok
27 Correct 754 ms 23028 KB Ok
28 Correct 375 ms 11680 KB Ok
29 Correct 749 ms 23580 KB Ok
30 Correct 47 ms 1656 KB Ok
31 Correct 5 ms 504 KB Ok
32 Correct 24 ms 1016 KB Ok
33 Correct 93 ms 3196 KB Ok
34 Correct 3 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 370 ms 11512 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 11580 KB Ok
2 Correct 748 ms 23312 KB Ok
3 Correct 763 ms 23300 KB Ok
4 Correct 47 ms 1784 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 92 ms 3064 KB Ok
7 Correct 743 ms 23388 KB Ok
8 Correct 5 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 5 ms 504 KB Ok
11 Correct 185 ms 5960 KB Ok
12 Correct 376 ms 11640 KB Ok