oj.uz

Submission #290998

# Submission time Handle Problem Language Result Execution time Memory
290998 2020-09-04T15:20:56 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
69 / 100
 1000 ms 18884 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() <= 600) {
		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 1 ms 256 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 736 KB Ok
2 Correct 595 ms 7528 KB Ok
3 Correct 629 ms 4080 KB Ok
4 Correct 600 ms 376 KB Ok
5 Correct 596 ms 504 KB Ok
6 Correct 593 ms 508 KB Ok
7 Correct 595 ms 712 KB Ok
8 Correct 625 ms 3980 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 18664 KB Ok
2 Correct 286 ms 9328 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 0 ms 256 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 256 KB Ok
2 Correct 15 ms 896 KB Ok
3 Correct 533 ms 9360 KB Ok
4 Correct 213 ms 4852 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 4 ms 384 KB Ok
7 Correct 127 ms 2548 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 18808 KB Ok
2 Correct 728 ms 18696 KB Ok
3 Correct 942 ms 18844 KB Ok
4 Correct 336 ms 9612 KB Ok
5 Correct 472 ms 9504 KB Ok
6 Correct 167 ms 4764 KB Ok
7 Correct 144 ms 4724 KB Ok
8 Correct 166 ms 2536 KB Ok
9 Correct 87 ms 2520 KB Ok
10 Correct 33 ms 1408 KB Ok
11 Correct 3 ms 384 KB Ok
12 Correct 2 ms 384 KB Ok
13 Correct 1 ms 384 KB Ok

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 18664 KB Ok
2 Correct 286 ms 9328 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 0 ms 256 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 256 KB Ok
7 Correct 15 ms 896 KB Ok
8 Correct 533 ms 9360 KB Ok
9 Correct 213 ms 4852 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 4 ms 384 KB Ok
12 Correct 127 ms 2548 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 880 ms 18808 KB Ok
15 Correct 728 ms 18696 KB Ok
16 Correct 942 ms 18844 KB Ok
17 Correct 336 ms 9612 KB Ok
18 Correct 472 ms 9504 KB Ok
19 Correct 167 ms 4764 KB Ok
20 Correct 144 ms 4724 KB Ok
21 Correct 166 ms 2536 KB Ok
22 Correct 87 ms 2520 KB Ok
23 Correct 33 ms 1408 KB Ok
24 Correct 3 ms 384 KB Ok
25 Correct 2 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 693 ms 18664 KB Ok
28 Correct 333 ms 9420 KB Ok
29 Execution timed out 1079 ms 17632 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 9420 KB Ok
2 Correct 679 ms 18716 KB Ok
3 Correct 940 ms 18884 KB Ok
4 Correct 38 ms 1400 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 268 ms 2540 KB Ok
7 Correct 670 ms 18796 KB Ok
8 Correct 3 ms 384 KB Ok
9 Correct 1 ms 384 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 137 ms 4852 KB Ok
12 Correct 325 ms 9584 KB Ok