oj.uz

Submission #291002

# Submission time Handle Problem Language Result Execution time Memory
291002 2020-09-04T15:22:50 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
69 / 100
 990 ms 18852 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(!t || 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);
		}
		if(!t && elapsed() >= 900) 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 594 ms 584 KB Ok
2 Correct 603 ms 7624 KB Ok
3 Correct 911 ms 4096 KB Ok
4 Correct 598 ms 376 KB Ok
5 Correct 892 ms 392 KB Ok
6 Correct 594 ms 504 KB Ok
7 Correct 895 ms 792 KB Ok
8 Correct 604 ms 4104 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 18664 KB Ok
2 Correct 289 ms 9456 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 17 ms 928 KB Ok
3 Correct 562 ms 9444 KB Ok
4 Correct 163 ms 4836 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 4 ms 384 KB Ok
7 Correct 143 ms 2700 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 18840 KB Ok
2 Correct 912 ms 18752 KB Ok
3 Correct 840 ms 18652 KB Ok
4 Correct 330 ms 9388 KB Ok
5 Correct 426 ms 9328 KB Ok
6 Correct 160 ms 4832 KB Ok
7 Correct 178 ms 4812 KB Ok
8 Correct 170 ms 2536 KB Ok
9 Correct 77 ms 2564 KB Ok
10 Correct 39 ms 1432 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
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 18664 KB Ok
2 Correct 289 ms 9456 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 17 ms 928 KB Ok
8 Correct 562 ms 9444 KB Ok
9 Correct 163 ms 4836 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 4 ms 384 KB Ok
12 Correct 143 ms 2700 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 717 ms 18840 KB Ok
15 Correct 912 ms 18752 KB Ok
16 Correct 840 ms 18652 KB Ok
17 Correct 330 ms 9388 KB Ok
18 Correct 426 ms 9328 KB Ok
19 Correct 160 ms 4832 KB Ok
20 Correct 178 ms 4812 KB Ok
21 Correct 170 ms 2536 KB Ok
22 Correct 77 ms 2564 KB Ok
23 Correct 39 ms 1432 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 681 ms 18704 KB Ok
28 Correct 335 ms 9588 KB Ok
29 Incorrect 908 ms 7712 KB Output -1 while solution exists
30 Halted 0 ms 0 KB -

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 9468 KB Ok
2 Correct 676 ms 18764 KB Ok
3 Correct 990 ms 18780 KB Ok
4 Correct 31 ms 1400 KB Ok
5 Correct 1 ms 288 KB Ok
6 Correct 97 ms 2524 KB Ok
7 Correct 791 ms 18852 KB Ok
8 Correct 3 ms 384 KB Ok
9 Correct 1 ms 256 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 148 ms 4724 KB Ok
12 Correct 327 ms 9328 KB Ok