oj.uz

Submission #291022

# Submission time Handle Problem Language Result Execution time Memory
291022 2020-09-04T15:39:48 Z PeppaPig "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 674 ms 7928 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);
	if(k % 2 == 0) return !printf("-1\n");

	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 0 ms 384 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Ok
2 Correct 0 ms 256 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 0 ms 384 KB Ok
6 Correct 1 ms 256 KB Ok
7 Correct 0 ms 256 KB Ok
8 Correct 1 ms 256 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 7416 KB Ok
2 Correct 274 ms 3708 KB Ok
3 Correct 3 ms 384 KB Ok
4 Correct 0 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 0 ms 384 KB Ok
2 Correct 14 ms 568 KB Ok
3 Correct 293 ms 3824 KB Ok
4 Correct 131 ms 1996 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 5 ms 384 KB Ok
7 Correct 61 ms 1148 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 7788 KB Ok
2 Correct 574 ms 7692 KB Ok
3 Correct 611 ms 7544 KB Ok
4 Correct 294 ms 3960 KB Ok
5 Correct 276 ms 3832 KB Ok
6 Correct 123 ms 2040 KB Ok
7 Correct 136 ms 1912 KB Ok
8 Correct 59 ms 1144 KB Ok
9 Correct 59 ms 1144 KB Ok
10 Correct 29 ms 768 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 583 ms 7416 KB Ok
2 Correct 274 ms 3708 KB Ok
3 Correct 3 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 0 ms 384 KB Ok
7 Correct 14 ms 568 KB Ok
8 Correct 293 ms 3824 KB Ok
9 Correct 131 ms 1996 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 5 ms 384 KB Ok
12 Correct 61 ms 1148 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 674 ms 7788 KB Ok
15 Correct 574 ms 7692 KB Ok
16 Correct 611 ms 7544 KB Ok
17 Correct 294 ms 3960 KB Ok
18 Correct 276 ms 3832 KB Ok
19 Correct 123 ms 2040 KB Ok
20 Correct 136 ms 1912 KB Ok
21 Correct 59 ms 1144 KB Ok
22 Correct 59 ms 1144 KB Ok
23 Correct 29 ms 768 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 558 ms 7416 KB Ok
28 Correct 277 ms 3832 KB Ok
29 Correct 593 ms 7928 KB Ok
30 Correct 28 ms 760 KB Ok
31 Correct 2 ms 384 KB Ok
32 Correct 14 ms 512 KB Ok
33 Correct 61 ms 1144 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 0 ms 384 KB Ok
38 Correct 304 ms 3704 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 3832 KB Ok
2 Correct 603 ms 7416 KB Ok
3 Correct 591 ms 7672 KB Ok
4 Correct 28 ms 768 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 60 ms 1144 KB Ok
7 Correct 573 ms 7544 KB Ok
8 Correct 2 ms 384 KB Ok
9 Correct 0 ms 384 KB Ok
10 Correct 2 ms 384 KB Ok
11 Correct 123 ms 1936 KB Ok
12 Correct 281 ms 3832 KB Ok