oj.uz

Submission #287949

# Submission time Handle Problem Language Result Execution time Memory
287949 2020-09-01T07:10:59 Z bensonlzl "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 223 ms 15984 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(1351273);

int N, K, T, S;
string st;
int usable[1000005];
vector<int> kdiff, ans;

void dfs(int x){
	usable[x] = 0;
	ans.push_back(x);
	for (auto it : kdiff){
		if (usable[x ^ it]){
			dfs(x ^ it);
			return;
		}
	}
}

string intToString(int x){
	string r;
	for (int i = 0; i < N; ++i){
		r = ((x & (1 << i)) ? '1' : '0') + r;
	}
	return r;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K >> T;
	cin >> st;
	for (int i = 0; i < (int) st.size(); ++i){
		S *= 2;
		S += (int) (st[i]-'0');
	}
	for (int i = 0; i < (1 << N); ++i){
		if (__builtin_popcount(i) == K){
			kdiff.push_back(i);
		}
		usable[i] = 1;
	}
	shuffle(kdiff.begin(),kdiff.end(),rng);
	dfs(S);
	if ((int) ans.size() != (1 << N)){
		cout << -1 << '\n';
	}
	else{
		cout << (1 << N) << '\n';
		for (auto it : ans){
			cout << intToString(it) << '\n';
		}
	}
}

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 1 ms 544 KB Ok
2 Correct 9 ms 6144 KB Ok
3 Correct 5 ms 3452 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 0 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 1 ms 512 KB Ok
8 Correct 6 ms 3360 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 15728 KB Ok
2 Correct 93 ms 7924 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 1 ms 352 KB Ok
5 Correct 0 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 5 ms 768 KB Ok
3 Correct 91 ms 7932 KB Ok
4 Correct 44 ms 4220 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 512 KB Ok
7 Correct 19 ms 2296 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 15848 KB Ok
2 Correct 223 ms 15720 KB Ok
3 Correct 201 ms 15856 KB Ok
4 Correct 94 ms 8048 KB Ok
5 Correct 93 ms 7928 KB Ok
6 Correct 43 ms 4376 KB Ok
7 Correct 42 ms 4216 KB Ok
8 Correct 21 ms 2320 KB Ok
9 Correct 19 ms 2304 KB Ok
10 Correct 10 ms 1280 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 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 210 ms 15728 KB Ok
2 Correct 93 ms 7924 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 1 ms 352 KB Ok
5 Correct 0 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 5 ms 768 KB Ok
8 Correct 91 ms 7932 KB Ok
9 Correct 44 ms 4220 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 1 ms 512 KB Ok
12 Correct 19 ms 2296 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 207 ms 15848 KB Ok
15 Correct 223 ms 15720 KB Ok
16 Correct 201 ms 15856 KB Ok
17 Correct 94 ms 8048 KB Ok
18 Correct 93 ms 7928 KB Ok
19 Correct 43 ms 4376 KB Ok
20 Correct 42 ms 4216 KB Ok
21 Correct 21 ms 2320 KB Ok
22 Correct 19 ms 2304 KB Ok
23 Correct 10 ms 1280 KB Ok
24 Correct 1 ms 384 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 220 ms 15984 KB Ok
28 Correct 94 ms 8064 KB Ok
29 Correct 203 ms 15848 KB Ok
30 Correct 9 ms 1280 KB Ok
31 Correct 1 ms 384 KB Ok
32 Correct 5 ms 768 KB Ok
33 Correct 19 ms 2304 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 92 ms 7932 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7924 KB Ok
2 Correct 221 ms 15740 KB Ok
3 Correct 211 ms 15976 KB Ok
4 Correct 9 ms 1280 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 20 ms 2304 KB Ok
7 Correct 204 ms 15852 KB Ok
8 Correct 1 ms 384 KB Ok
9 Correct 1 ms 384 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 42 ms 4224 KB Ok
12 Correct 94 ms 8068 KB Ok