oj.uz

Submission #291015

# Submission time Handle Problem Language Result Execution time Memory
291015 2020-09-04T15:32:31 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 899 ms 7820 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 19;

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 chk[N], ans[N];

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);

		ans[0] = s;
		int ptr = 1;
		bool valid = true;
		for(int j = 0; j < n; j++) for(int i = ptr - 1; ~i; i--) {
			ans[ptr] = ans[i] ^ base[j];
			if(!chk[ans[ptr]]) chk[ans[ptr]] = 1;
			else {
				valid = false;
				break;
			}
			++ptr;
		}

		if(valid) {
			printf("%d\n", (1 << n));
			for(int i = 0; i < (1 << n); i++) print(ans[i]);
			exit(0);
		} else for(int i = 0; i < (1 << n); i++) chk[ans[i]] = 0;
		if(!t && elapsed() >= 900) break;
	}
	printf("-1\n");

	return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  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 384 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 424 KB Ok
2 Correct 602 ms 1920 KB Ok
3 Correct 896 ms 1304 KB Ok
4 Correct 597 ms 376 KB Ok
5 Correct 899 ms 384 KB Ok
6 Correct 596 ms 384 KB Ok
7 Correct 895 ms 440 KB Ok
8 Correct 602 ms 1152 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 7468 KB Ok
2 Correct 265 ms 3704 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 ms 384 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 512 KB Ok
3 Correct 270 ms 3860 KB Ok
4 Correct 125 ms 1912 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 3 ms 384 KB Ok
7 Correct 58 ms 1176 KB Ok
8 Correct 1 ms 288 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 7800 KB Ok
2 Correct 603 ms 7544 KB Ok
3 Correct 577 ms 7584 KB Ok
4 Correct 296 ms 4160 KB Ok
5 Correct 278 ms 3704 KB Ok
6 Correct 125 ms 2040 KB Ok
7 Correct 126 ms 1916 KB Ok
8 Correct 58 ms 1144 KB Ok
9 Correct 66 ms 1176 KB Ok
10 Correct 29 ms 760 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 558 ms 7468 KB Ok
2 Correct 265 ms 3704 KB Ok
3 Correct 2 ms 384 KB Ok
4 Correct 1 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 17 ms 512 KB Ok
8 Correct 270 ms 3860 KB Ok
9 Correct 125 ms 1912 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 3 ms 384 KB Ok
12 Correct 58 ms 1176 KB Ok
13 Correct 1 ms 288 KB Ok
14 Correct 607 ms 7800 KB Ok
15 Correct 603 ms 7544 KB Ok
16 Correct 577 ms 7584 KB Ok
17 Correct 296 ms 4160 KB Ok
18 Correct 278 ms 3704 KB Ok
19 Correct 125 ms 2040 KB Ok
20 Correct 126 ms 1916 KB Ok
21 Correct 58 ms 1144 KB Ok
22 Correct 66 ms 1176 KB Ok
23 Correct 29 ms 760 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 574 ms 7440 KB Ok
28 Correct 271 ms 3704 KB Ok
29 Correct 600 ms 7820 KB Ok
30 Correct 28 ms 764 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 15 ms 512 KB Ok
33 Correct 63 ms 1272 KB Ok
34 Correct 1 ms 384 KB Ok
35 Correct 0 ms 384 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 0 ms 384 KB Ok
38 Correct 309 ms 3732 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 3832 KB Ok
2 Correct 564 ms 7516 KB Ok
3 Correct 614 ms 7788 KB Ok
4 Correct 30 ms 680 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 82 ms 1144 KB Ok
7 Correct 699 ms 7532 KB Ok
8 Correct 2 ms 384 KB Ok
9 Correct 1 ms 384 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 134 ms 1912 KB Ok
12 Correct 321 ms 3720 KB Ok