oj.uz

Submission #290970

# Submission time Handle Problem Language Result Execution time Memory
290970 2020-09-04T15:09:34 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
83 / 100
 896 ms 19016 KB 
#include <bits/stdc++.h>

using namespace std;

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");
}

chrono::steady_clock::time_point start;

chrono::steady_clock::time_point get_now() {
	return chrono::steady_clock::now();
}

int elapsed() {
	return (int)chrono::duration_cast<chrono::milliseconds>(get_now() - start).count();
}

int main() {
	start = get_now();

	char input[100];
	scanf("%d %d %d %s", &n, &k, &t, input);
	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(elapsed() <= 500) {
		shuffle(base.begin(), base.end(), rng);

		vector<int> ans = {s};
		for(int j = 0; j < n; j++)
			for(int i = (int)ans.size() - 1; ~i; i--)
				ans.emplace_back(ans[i] ^ base[j]);

		set<int> st(ans.begin(), ans.end());
		if((int)st.size() == (1 << n)) {
			printf("%d\n", (1 << n));
			for(int x : ans) print(x);
			exit(0);
		}
	}
	printf("-1\n");

	return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  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 256 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 608 KB Ok
2 Correct 534 ms 7512 KB Ok
3 Correct 525 ms 4056 KB Ok
4 Correct 501 ms 256 KB Ok
5 Correct 502 ms 384 KB Ok
6 Correct 500 ms 512 KB Ok
7 Correct 497 ms 632 KB Ok
8 Correct 494 ms 4040 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 18704 KB Ok
2 Correct 295 ms 9328 KB Ok
3 Correct 2 ms 512 KB Ok
4 Correct 0 ms 256 KB Ok
5 Correct 1 ms 256 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Ok
2 Correct 19 ms 828 KB Ok
3 Correct 602 ms 9464 KB Ok
4 Correct 184 ms 4980 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 4 ms 384 KB Ok
7 Correct 96 ms 2540 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 18888 KB Ok
2 Correct 669 ms 18792 KB Ok
3 Correct 793 ms 19016 KB Ok
4 Correct 307 ms 9456 KB Ok
5 Correct 339 ms 9308 KB Ok
6 Correct 139 ms 4880 KB Ok
7 Correct 133 ms 4852 KB Ok
8 Correct 66 ms 2552 KB Ok
9 Correct 88 ms 2504 KB Ok
10 Correct 32 ms 1420 KB Ok
11 Correct 2 ms 384 KB Ok
12 Correct 3 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 757 ms 18704 KB Ok
2 Correct 295 ms 9328 KB Ok
3 Correct 2 ms 512 KB Ok
4 Correct 0 ms 256 KB Ok
5 Correct 1 ms 256 KB Ok
6 Correct 1 ms 256 KB Ok
7 Correct 19 ms 828 KB Ok
8 Correct 602 ms 9464 KB Ok
9 Correct 184 ms 4980 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 4 ms 384 KB Ok
12 Correct 96 ms 2540 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 896 ms 18888 KB Ok
15 Correct 669 ms 18792 KB Ok
16 Correct 793 ms 19016 KB Ok
17 Correct 307 ms 9456 KB Ok
18 Correct 339 ms 9308 KB Ok
19 Correct 139 ms 4880 KB Ok
20 Correct 133 ms 4852 KB Ok
21 Correct 66 ms 2552 KB Ok
22 Correct 88 ms 2504 KB Ok
23 Correct 32 ms 1420 KB Ok
24 Correct 2 ms 384 KB Ok
25 Correct 3 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 663 ms 18796 KB Ok
28 Correct 468 ms 9468 KB Ok
29 Correct 866 ms 18780 KB Ok
30 Correct 33 ms 1400 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 22 ms 840 KB Ok
33 Correct 168 ms 2592 KB Ok
34 Correct 1 ms 384 KB Ok
35 Correct 1 ms 256 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 0 ms 256 KB Ok
38 Correct 610 ms 9512 KB Ok

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 4120 KB Output -1 while solution exists
2 Halted 0 ms 0 KB -