oj.uz

Submission #911218

# Submission time Handle Problem Language Result Execution time Memory
911218 2024-01-18T16:04:28 Z daoquanglinh2007 "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 184 ms 9808 KB 
#include <bits/stdc++.h>
using namespace std;

#define flipbit(x, i) x ^= (1<<(i))

const int a[] = {0, 1, 3, 2, 6, 7, 5, 4};

string bS;
int N, K, S, T;
vector <int> v, ans;
int cnt[262144];

vector <int> build(int N){
	if (N == 1){
		vector <int> ans = {0, 1};
		return ans;
	}
	vector <int> a = build(N-1);
	for (int i = 0; i < (1<<(N-1)); i++){
		a.push_back((1<<(N-1))+a[(1<<(N-1))-1-i]);
	}
	return a;
}

vector <int> solve(int N, int K){
	v = build(N);
	ans.clear();
	ans.push_back(0);
	for (int i = 1; i < (1<<N); i++){
		ans.push_back(ans[i-1]);
		for (int j = 0; j < N; j++)
			if (((v[i]^v[i-1])>>j)&1){
				for (int t = 0; t < K; t++)
					flipbit(ans[i], (j+t)%N);
			}
	}
	memset(cnt, 0, sizeof(cnt));
	bool ok = 1;
	for (int x : ans){
		if (cnt[x]){
			ok = 0;
			break;
		}
		cnt[x]++;
	}
	if (ok){
		return ans;
	}
	if (K%2 == 0) return {};
	if (N == 2*K){
		vector <int> tmp = solve(N-2, K), ans(0);
		for (int i = 0; i < (1<<N); i++){
			if (i == 0){
				ans.push_back(0);
				continue;
			}
			if (i&1) ans.push_back(ans.back()^((1<<K)-1));
			else if (i&3) ans.push_back(ans.back()^((1<<N)-(1<<K)));
			else ans.push_back(ans.back()^(tmp[i/4]<<1)^(tmp[i/4-1]<<1));
		}
		return ans;
	}
	if (K == 3){
		vector <int> tmp = solve(N-3, 3), ans = tmp;
		for (int i = 1; i < 8; i++){
			int x = ans.back()&((1<<(N-3))-1);
			x ^= (1<<(N-4))+(1<<(N-5));
			for (int j = 0; j < (1<<(N-3)); j++)
				ans.push_back((a[i]<<(N-3))+(x^tmp[j]));
		}
		return ans;
	}
	return {};
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K >> T >> bS;
	for (int i = 0; i < N; i++)
		if (bS[i] == '1') S += (1<<(N-1-i));
		
	vector <int> ans = solve(N, K);
	if (ans.empty()){
		cout << "-1\n";
		return 0;
	}
	cout << (1<<N) << '\n';
	for (int &x : ans){
		x ^= S;
		for (int i = N-1; i >= 0; i--)
			cout << ((x>>i)&1);
		cout << '\n';
	}
	return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Ok
2 Correct 23 ms 3672 KB Ok
3 Correct 7 ms 2400 KB Ok
4 Correct 1 ms 1372 KB Ok
5 Correct 1 ms 1372 KB Ok
6 Correct 1 ms 1368 KB Ok
7 Correct 1 ms 1372 KB Ok
8 Correct 11 ms 2628 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9620 KB Ok
2 Correct 77 ms 5400 KB Ok
3 Correct 1 ms 1372 KB Ok
4 Correct 1 ms 1372 KB Ok
5 Correct 2 ms 1372 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Ok
2 Correct 5 ms 1628 KB Ok
3 Correct 77 ms 5312 KB Ok
4 Correct 38 ms 3408 KB Ok
5 Correct 1 ms 1368 KB Ok
6 Correct 2 ms 1368 KB Ok
7 Correct 18 ms 2272 KB Ok
8 Correct 1 ms 1372 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 9548 KB Ok
2 Correct 167 ms 9628 KB Ok
3 Correct 184 ms 9540 KB Ok
4 Correct 81 ms 5460 KB Ok
5 Correct 79 ms 5464 KB Ok
6 Correct 38 ms 3408 KB Ok
7 Correct 37 ms 3360 KB Ok
8 Correct 27 ms 2272 KB Ok
9 Correct 28 ms 2396 KB Ok
10 Correct 9 ms 1884 KB Ok
11 Correct 1 ms 1372 KB Ok
12 Correct 1 ms 1372 KB Ok
13 Correct 1 ms 1372 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9620 KB Ok
2 Correct 77 ms 5400 KB Ok
3 Correct 1 ms 1372 KB Ok
4 Correct 1 ms 1372 KB Ok
5 Correct 2 ms 1372 KB Ok
6 Correct 1 ms 1372 KB Ok
7 Correct 5 ms 1628 KB Ok
8 Correct 77 ms 5312 KB Ok
9 Correct 38 ms 3408 KB Ok
10 Correct 1 ms 1368 KB Ok
11 Correct 2 ms 1368 KB Ok
12 Correct 18 ms 2272 KB Ok
13 Correct 1 ms 1372 KB Ok
14 Correct 168 ms 9548 KB Ok
15 Correct 167 ms 9628 KB Ok
16 Correct 184 ms 9540 KB Ok
17 Correct 81 ms 5460 KB Ok
18 Correct 79 ms 5464 KB Ok
19 Correct 38 ms 3408 KB Ok
20 Correct 37 ms 3360 KB Ok
21 Correct 27 ms 2272 KB Ok
22 Correct 28 ms 2396 KB Ok
23 Correct 9 ms 1884 KB Ok
24 Correct 1 ms 1372 KB Ok
25 Correct 1 ms 1372 KB Ok
26 Correct 1 ms 1372 KB Ok
27 Correct 180 ms 9636 KB Ok
28 Correct 88 ms 5464 KB Ok
29 Correct 172 ms 9544 KB Ok
30 Correct 10 ms 1884 KB Ok
31 Correct 1 ms 1624 KB Ok
32 Correct 5 ms 1628 KB Ok
33 Correct 20 ms 2396 KB Ok
34 Correct 1 ms 1372 KB Ok
35 Correct 1 ms 1372 KB Ok
36 Correct 1 ms 1372 KB Ok
37 Correct 1 ms 1372 KB Ok
38 Correct 86 ms 5444 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5460 KB Ok
2 Correct 179 ms 9548 KB Ok
3 Correct 175 ms 9664 KB Ok
4 Correct 10 ms 1880 KB Ok
5 Correct 1 ms 1372 KB Ok
6 Correct 20 ms 2392 KB Ok
7 Correct 166 ms 9808 KB Ok
8 Correct 1 ms 1368 KB Ok
9 Correct 1 ms 1372 KB Ok
10 Correct 1 ms 1372 KB Ok
11 Correct 42 ms 3496 KB Ok
12 Correct 86 ms 5460 KB Ok