oj.uz

Submission #441181

# Submission time Handle Problem Language Result Execution time Memory
441181 2021-07-04T13:23:06 Z 8e7 "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 327 ms 7432 KB 
//Challenge: Accepted
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <utility>
#include <assert.h>
using namespace std;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 400005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> ans, v;
void build(int n) {
	v.push_back(0);
	int cur = 0;
	for (int i = 1;i < (1<<n);i++) {
		cur ^= i & (-i);	
		v.push_back(cur);
	}	
}
void print(int x, int n) {
	for (int i = 0;i < n;i++) cout << ((x & (1<<i)) ? 1 : 0);
	cout << "\n";
}
void solve(int n, int k, int se) {
	//debug(n, k);
	//print(se, 6);
	if (n == k + 1) {
		for (int i = 0;i < v.size();i++) ans.push_back(se ^ v[i]);
		return;
	}
	solve(n - 1, k, se);
	int cnt = 0, tmp = ans.back() ^ se;
	for (int i = 0;i < n;i++) {
		if ((ans.back() ^ se) & (1<<i)) {
			if (cnt < k - 1) tmp ^= (1<<i), cnt++; 
		}
	}
	tmp ^= (1<<(n - 1));
	solve(n - 1, k, se ^ tmp);
}
	
int main() {
	io
	int n, k, cy;
	cin >> n >> k >> cy;
	int st = 0;
	for (int i = 0;i < n;i++) {
		char c;
		cin >> c;
		st += (1<<i) * (c - '0');
	}
	if (k % 2 == 0) {
		cout << -1 << "\n";
		return 0;
	}
	cout << (1<<n) << "\n";
	if (k == 1) {
		build(n);
		for (int i = 0;i < (1<<n);i++) print(v[i] ^ st, n);
	} else {
		build(k + 1);	
		for (int i = 1;i < (1<<(k + 1));i+=2) {
			v[i] ^= (1<<(k + 1)) - 1;
		}
		solve(n, k, 0);	
		for (int i:ans) print(i ^ st, n);
	}
}

Compilation message

lyuboyn.cpp: In function 'void solve(int, int, int)':
lyuboyn.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0;i < v.size();i++) ans.push_back(se ^ v[i]);
      |                  ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 1 ms 204 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 1 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 278 ms 6380 KB Ok
2 Correct 153 ms 3268 KB Ok
3 Correct 1 ms 204 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 8 ms 460 KB Ok
3 Correct 129 ms 3252 KB Ok
4 Correct 60 ms 1700 KB Ok
5 Correct 2 ms 204 KB Ok
6 Correct 2 ms 308 KB Ok
7 Correct 52 ms 1020 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 6404 KB Ok
2 Correct 268 ms 6452 KB Ok
3 Correct 263 ms 6464 KB Ok
4 Correct 126 ms 3264 KB Ok
5 Correct 133 ms 3252 KB Ok
6 Correct 59 ms 1796 KB Ok
7 Correct 74 ms 1732 KB Ok
8 Correct 28 ms 972 KB Ok
9 Correct 47 ms 1016 KB Ok
10 Correct 14 ms 588 KB Ok
11 Correct 1 ms 332 KB Ok
12 Correct 1 ms 332 KB Ok
13 Correct 1 ms 204 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 6380 KB Ok
2 Correct 153 ms 3268 KB Ok
3 Correct 1 ms 204 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 8 ms 460 KB Ok
8 Correct 129 ms 3252 KB Ok
9 Correct 60 ms 1700 KB Ok
10 Correct 2 ms 204 KB Ok
11 Correct 2 ms 308 KB Ok
12 Correct 52 ms 1020 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 268 ms 6404 KB Ok
15 Correct 268 ms 6452 KB Ok
16 Correct 263 ms 6464 KB Ok
17 Correct 126 ms 3264 KB Ok
18 Correct 133 ms 3252 KB Ok
19 Correct 59 ms 1796 KB Ok
20 Correct 74 ms 1732 KB Ok
21 Correct 28 ms 972 KB Ok
22 Correct 47 ms 1016 KB Ok
23 Correct 14 ms 588 KB Ok
24 Correct 1 ms 332 KB Ok
25 Correct 1 ms 332 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 295 ms 7408 KB Ok
28 Correct 130 ms 3264 KB Ok
29 Correct 279 ms 6420 KB Ok
30 Correct 14 ms 588 KB Ok
31 Correct 2 ms 332 KB Ok
32 Correct 7 ms 460 KB Ok
33 Correct 29 ms 1164 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 1 ms 204 KB Ok
36 Correct 1 ms 204 KB Ok
37 Correct 0 ms 312 KB Ok
38 Correct 127 ms 3540 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 3472 KB Ok
2 Correct 272 ms 7432 KB Ok
3 Correct 327 ms 6472 KB Ok
4 Correct 14 ms 652 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 29 ms 1080 KB Ok
7 Correct 268 ms 6524 KB Ok
8 Correct 2 ms 332 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 62 ms 2048 KB Ok
12 Correct 124 ms 3384 KB Ok