oj.uz

Submission #290978

# Submission time Handle Problem Language Result Execution time Memory
290978 2020-09-04T15:12:13 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
69 / 100
 1000 ms 18996 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() >= 990) 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 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 963 ms 592 KB Ok
2 Correct 996 ms 7812 KB Ok
3 Correct 986 ms 4084 KB Ok
4 Correct 972 ms 368 KB Ok
5 Correct 983 ms 504 KB Ok
6 Correct 988 ms 504 KB Ok
7 Correct 988 ms 696 KB Ok
8 Correct 995 ms 4068 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 18724 KB Ok
2 Correct 295 ms 9332 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 384 KB Ok
2 Correct 16 ms 800 KB Ok
3 Correct 418 ms 9444 KB Ok
4 Correct 165 ms 4836 KB Ok
5 Correct 2 ms 384 KB Ok
6 Correct 4 ms 384 KB Ok
7 Correct 82 ms 2660 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 18832 KB Ok
2 Correct 689 ms 18904 KB Ok
3 Correct 665 ms 18668 KB Ok
4 Correct 304 ms 9584 KB Ok
5 Correct 390 ms 9428 KB Ok
6 Correct 162 ms 4892 KB Ok
7 Correct 135 ms 4724 KB Ok
8 Correct 66 ms 2552 KB Ok
9 Correct 84 ms 2632 KB Ok
10 Correct 31 ms 1400 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
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 18724 KB Ok
2 Correct 295 ms 9332 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 384 KB Ok
7 Correct 16 ms 800 KB Ok
8 Correct 418 ms 9444 KB Ok
9 Correct 165 ms 4836 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 4 ms 384 KB Ok
12 Correct 82 ms 2660 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 675 ms 18832 KB Ok
15 Correct 689 ms 18904 KB Ok
16 Correct 665 ms 18668 KB Ok
17 Correct 304 ms 9584 KB Ok
18 Correct 390 ms 9428 KB Ok
19 Correct 162 ms 4892 KB Ok
20 Correct 135 ms 4724 KB Ok
21 Correct 66 ms 2552 KB Ok
22 Correct 84 ms 2632 KB Ok
23 Correct 31 ms 1400 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 662 ms 18836 KB Ok
28 Correct 337 ms 9452 KB Ok
29 Execution timed out 1072 ms 18920 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 9304 KB Ok
2 Correct 655 ms 18996 KB Ok
3 Correct 706 ms 18796 KB Ok
4 Correct 42 ms 1560 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 163 ms 2476 KB Ok
7 Correct 736 ms 18708 KB Ok
8 Correct 3 ms 384 KB Ok
9 Correct 0 ms 256 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 137 ms 4836 KB Ok
12 Correct 468 ms 9364 KB Ok