oj.uz

Submission #291042

# Submission time Handle Problem Language Result Execution time Memory
291042 2020-09-04T15:51:22 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 602 ms 7704 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 19;

int n, k, t, s;
mt19937 rng(time(NULL));

void print(int val) {
	vector<int> vec;
	for(int i = 0; i < n; i++, val >>= 1)
		vec.emplace_back(val & 1);
	reverse(vec.begin(), vec.end());
	for(int x : vec) printf("%d", x);
	printf("\n");
}

int chk[N], ans[N];
vector<int> base;

bool is_basis() {
	vector<int> mat(base.begin(), base.begin() + n);
	for(int i = n - 1; ~i; i--) {
		int val = -1;
		for(int x : mat) if(x >> i & 1) val = x;
		if(val == -1) return false;
		for(int &x : mat) if(x != val && (x >> i & 1))
			x ^= val;	
	}
	return true;
}

int main() {
	char input[100];
	scanf("%d %d %d %s", &n, &k, &t, input);
	if(k % 2 == 0) return !printf("-1\n");

	for(int i = 0; input[i] != '\0'; i++)
		s = (s << 1) + (input[i] == '1');

	for(int i = 0; i < (1 << n); i++) if(__builtin_popcount(i) == k)
		base.emplace_back(i);

	while(true) {
		shuffle(base.begin(), base.end(), rng);
		if(!is_basis()) continue;

		ans[0] = s;
		int ptr = 1, valid = 1;
		for(int j = 0; j < n; j++) for(int i = ptr - 1; ~i; i--) {
			ans[ptr] = ans[i] ^ base[j];
			if(!chk[ans[ptr]]) chk[ans[ptr]] = 1;
			else {
				valid = 0;
				break;
			}
			++ptr;
		}

		if(valid) {
			printf("%d\n", (1 << n));
			for(int i = 0; i < (1 << n); i++) print(ans[i]);
			exit(0);
		} else for(int i = 0; i < (1 << n); i++) chk[ans[i]] = 0;
	}

	return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%d %d %d %s", &n, &k, &t, input);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 7416 KB Ok
2 Correct 258 ms 3704 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Ok
2 Correct 18 ms 512 KB Ok
3 Correct 292 ms 3788 KB Ok
4 Correct 141 ms 2040 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 3 ms 384 KB Ok
7 Correct 60 ms 1144 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 7704 KB Ok
2 Correct 557 ms 7500 KB Ok
3 Correct 546 ms 7416 KB Ok
4 Correct 278 ms 3960 KB Ok
5 Correct 266 ms 3752 KB Ok
6 Correct 126 ms 2040 KB Ok
7 Correct 129 ms 1912 KB Ok
8 Correct 58 ms 1144 KB Ok
9 Correct 57 ms 1144 KB Ok
10 Correct 31 ms 768 KB Ok
11 Correct 2 ms 384 KB Ok
12 Correct 2 ms 384 KB Ok
13 Correct 1 ms 384 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 7416 KB Ok
2 Correct 258 ms 3704 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 18 ms 512 KB Ok
8 Correct 292 ms 3788 KB Ok
9 Correct 141 ms 2040 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 3 ms 384 KB Ok
12 Correct 60 ms 1144 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 592 ms 7704 KB Ok
15 Correct 557 ms 7500 KB Ok
16 Correct 546 ms 7416 KB Ok
17 Correct 278 ms 3960 KB Ok
18 Correct 266 ms 3752 KB Ok
19 Correct 126 ms 2040 KB Ok
20 Correct 129 ms 1912 KB Ok
21 Correct 58 ms 1144 KB Ok
22 Correct 57 ms 1144 KB Ok
23 Correct 31 ms 768 KB Ok
24 Correct 2 ms 384 KB Ok
25 Correct 2 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 576 ms 7348 KB Ok
28 Correct 268 ms 3704 KB Ok
29 Correct 599 ms 7688 KB Ok
30 Correct 39 ms 760 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 13 ms 512 KB Ok
33 Correct 60 ms 1144 KB Ok
34 Correct 1 ms 384 KB Ok
35 Correct 1 ms 384 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 0 ms 384 KB Ok
38 Correct 298 ms 3704 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 3796 KB Ok
2 Correct 536 ms 7364 KB Ok
3 Correct 602 ms 7696 KB Ok
4 Correct 27 ms 768 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 65 ms 1124 KB Ok
7 Correct 556 ms 7484 KB Ok
8 Correct 2 ms 384 KB Ok
9 Correct 0 ms 384 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 120 ms 1912 KB Ok
12 Correct 271 ms 3728 KB Ok