oj.uz

Submission #290982

# Submission time Handle Problem Language Result Execution time Memory
290982 2020-09-04T15:14:54 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
83 / 100
 1000 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(true) {
		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);
		}
		if(elapsed() >= 800) break;
	}
	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 792 ms 704 KB Ok
2 Correct 813 ms 7640 KB Ok
3 Correct 805 ms 4128 KB Ok
4 Correct 795 ms 256 KB Ok
5 Correct 792 ms 392 KB Ok
6 Correct 795 ms 384 KB Ok
7 Correct 796 ms 592 KB Ok
8 Correct 808 ms 3980 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 18724 KB Ok
2 Correct 295 ms 9348 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 ms 256 KB Ok
5 Correct 1 ms 288 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Ok
2 Correct 23 ms 800 KB Ok
3 Correct 359 ms 9364 KB Ok
4 Correct 189 ms 4740 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 5 ms 384 KB Ok
7 Correct 96 ms 2536 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 19016 KB Ok
2 Correct 741 ms 18704 KB Ok
3 Correct 950 ms 18732 KB Ok
4 Correct 332 ms 9580 KB Ok
5 Correct 386 ms 9344 KB Ok
6 Correct 189 ms 4952 KB Ok
7 Correct 141 ms 4780 KB Ok
8 Correct 73 ms 2536 KB Ok
9 Correct 77 ms 2588 KB Ok
10 Correct 45 ms 1440 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 666 ms 18724 KB Ok
2 Correct 295 ms 9348 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 ms 256 KB Ok
5 Correct 1 ms 288 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 23 ms 800 KB Ok
8 Correct 359 ms 9364 KB Ok
9 Correct 189 ms 4740 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 5 ms 384 KB Ok
12 Correct 96 ms 2536 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 701 ms 19016 KB Ok
15 Correct 741 ms 18704 KB Ok
16 Correct 950 ms 18732 KB Ok
17 Correct 332 ms 9580 KB Ok
18 Correct 386 ms 9344 KB Ok
19 Correct 189 ms 4952 KB Ok
20 Correct 141 ms 4780 KB Ok
21 Correct 73 ms 2536 KB Ok
22 Correct 77 ms 2588 KB Ok
23 Correct 45 ms 1440 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 656 ms 18668 KB Ok
28 Correct 414 ms 9504 KB Ok
29 Correct 695 ms 18796 KB Ok
30 Correct 31 ms 1400 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 24 ms 840 KB Ok
33 Correct 221 ms 2540 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 1 ms 384 KB Ok
38 Correct 647 ms 9468 KB Ok

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 9484 KB Time limit exceeded
2 Halted 0 ms 0 KB -