oj.uz

Submission #291030

# Submission time Handle Problem Language Result Execution time Memory
291030 2020-09-04T15:43:26 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 617 ms 7928 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];

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');

	vector<int> base;
	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);

		ans[0] = s;
		int ptr = 1;
		bool valid = true;
		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 = false;
				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:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d %d %d %s", &n, &k, &t, input);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 384 KB Ok
3 Correct 0 ms 384 KB Ok
4 Correct 1 ms 256 KB Ok
5 Correct 0 ms 384 KB Ok
6 Correct 1 ms 256 KB Ok
7 Correct 1 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 574 ms 7556 KB Ok
2 Correct 256 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 13 ms 552 KB Ok
3 Correct 272 ms 3796 KB Ok
4 Correct 123 ms 2072 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 4 ms 384 KB Ok
7 Correct 59 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 617 ms 7640 KB Ok
2 Correct 555 ms 7544 KB Ok
3 Correct 543 ms 7416 KB Ok
4 Correct 284 ms 3960 KB Ok
5 Correct 261 ms 3832 KB Ok
6 Correct 118 ms 2044 KB Ok
7 Correct 122 ms 2168 KB Ok
8 Correct 60 ms 1144 KB Ok
9 Correct 57 ms 1272 KB Ok
10 Correct 27 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 574 ms 7556 KB Ok
2 Correct 256 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 13 ms 552 KB Ok
8 Correct 272 ms 3796 KB Ok
9 Correct 123 ms 2072 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 4 ms 384 KB Ok
12 Correct 59 ms 1144 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 617 ms 7640 KB Ok
15 Correct 555 ms 7544 KB Ok
16 Correct 543 ms 7416 KB Ok
17 Correct 284 ms 3960 KB Ok
18 Correct 261 ms 3832 KB Ok
19 Correct 118 ms 2044 KB Ok
20 Correct 122 ms 2168 KB Ok
21 Correct 60 ms 1144 KB Ok
22 Correct 57 ms 1272 KB Ok
23 Correct 27 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 549 ms 7440 KB Ok
28 Correct 274 ms 3704 KB Ok
29 Correct 586 ms 7928 KB Ok
30 Correct 27 ms 768 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 14 ms 512 KB Ok
33 Correct 59 ms 1144 KB Ok
34 Correct 1 ms 384 KB Ok
35 Correct 0 ms 384 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 0 ms 384 KB Ok
38 Correct 272 ms 3704 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 3704 KB Ok
2 Correct 547 ms 7420 KB Ok
3 Correct 592 ms 7672 KB Ok
4 Correct 28 ms 768 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 62 ms 1148 KB Ok
7 Correct 571 ms 7416 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 269 ms 3864 KB Ok