oj.uz

Submission #290974

# Submission time Handle Problem Language Result Execution time Memory
290974 2020-09-04T15:10:37 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
52 / 100
 1000 ms 19160 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() <= 800) {
		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 795 ms 900 KB Ok
2 Correct 805 ms 7508 KB Ok
3 Correct 807 ms 4124 KB Ok
4 Correct 798 ms 376 KB Ok
5 Correct 795 ms 396 KB Ok
6 Correct 801 ms 384 KB Ok
7 Correct 802 ms 592 KB Ok
8 Correct 818 ms 4308 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 18804 KB Ok
2 Correct 303 ms 9456 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 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 21 ms 896 KB Ok
3 Correct 360 ms 9444 KB Ok
4 Correct 234 ms 4744 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 5 ms 384 KB Ok
7 Correct 90 ms 2516 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 18992 KB Ok
2 Correct 711 ms 18960 KB Ok
3 Correct 655 ms 18792 KB Ok
4 Correct 298 ms 9456 KB Ok
5 Correct 426 ms 9436 KB Ok
6 Correct 147 ms 4740 KB Ok
7 Correct 134 ms 4852 KB Ok
8 Correct 68 ms 2680 KB Ok
9 Correct 78 ms 2600 KB Ok
10 Correct 34 ms 1352 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 659 ms 18804 KB Ok
2 Correct 303 ms 9456 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 ms 256 KB Ok
5 Correct 1 ms 256 KB Ok
6 Correct 1 ms 256 KB Ok
7 Correct 21 ms 896 KB Ok
8 Correct 360 ms 9444 KB Ok
9 Correct 234 ms 4744 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 5 ms 384 KB Ok
12 Correct 90 ms 2516 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 860 ms 18992 KB Ok
15 Correct 711 ms 18960 KB Ok
16 Correct 655 ms 18792 KB Ok
17 Correct 298 ms 9456 KB Ok
18 Correct 426 ms 9436 KB Ok
19 Correct 147 ms 4740 KB Ok
20 Correct 134 ms 4852 KB Ok
21 Correct 68 ms 2680 KB Ok
22 Correct 78 ms 2600 KB Ok
23 Correct 34 ms 1352 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 649 ms 18792 KB Ok
28 Correct 325 ms 9332 KB Ok
29 Correct 760 ms 19160 KB Ok
30 Correct 41 ms 1368 KB Ok
31 Correct 3 ms 384 KB Ok
32 Correct 44 ms 844 KB Ok
33 Correct 345 ms 2540 KB Ok
34 Correct 1 ms 512 KB Ok
35 Correct 0 ms 256 KB Ok
36 Correct 2 ms 384 KB Ok
37 Correct 1 ms 256 KB Ok
38 Execution timed out 1020 ms 9396 KB Time limit exceeded

Subtask #8
0 / 17.0

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