oj.uz

Submission #911215

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

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

const int a[] = {0, 7, 9, 2, 5, 8, 3, 4, 10, 1, 6, 11, 12, 16, 23, 13, 17, 22, 15, 19, 20, 14, 18, 21, 24, 31, 39, 32, 43, 25, 30, 38, 33, 42, 27, 28, 36, 35, 40, 26, 29, 37, 34, 41, 46, 50, 53, 44, 48, 55, 45, 49, 54, 59, 60, 47, 57, 62, 51, 61, 58, 52, 63, 56};
const int b[] = {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%4 == 1 || i%4 == 3) ans.push_back(ans.back()^((1<<K)-1));
			if (i%4 == 2) ans.push_back(ans.back()^((1<<N)-(1<<K)));
			if (i%4 == 0){
				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((b[i]<<(N-3))+(x^tmp[j]));
		}
		return ans;
	}
	return {};
}

int main(){
//	freopen("LYUBOYN.inp", "r", stdin);
//	freopen("LYUBOYN.out", "w", stdout);
	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 1368 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Ok
2 Correct 22 ms 3676 KB Ok
3 Correct 6 ms 2656 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 9 ms 2652 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 9476 KB Ok
2 Correct 77 ms 5460 KB Ok
3 Correct 1 ms 1372 KB Ok
4 Correct 1 ms 1368 KB Ok
5 Correct 1 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 78 ms 5372 KB Ok
4 Correct 37 ms 3660 KB Ok
5 Correct 1 ms 1372 KB Ok
6 Correct 2 ms 1536 KB Ok
7 Correct 18 ms 2268 KB Ok
8 Correct 1 ms 1368 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 9524 KB Ok
2 Correct 167 ms 9696 KB Ok
3 Correct 165 ms 9412 KB Ok
4 Correct 79 ms 5460 KB Ok
5 Correct 78 ms 5456 KB Ok
6 Correct 39 ms 3436 KB Ok
7 Correct 37 ms 3408 KB Ok
8 Correct 19 ms 2268 KB Ok
9 Correct 19 ms 2400 KB Ok
10 Correct 10 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 161 ms 9476 KB Ok
2 Correct 77 ms 5460 KB Ok
3 Correct 1 ms 1372 KB Ok
4 Correct 1 ms 1368 KB Ok
5 Correct 1 ms 1372 KB Ok
6 Correct 1 ms 1372 KB Ok
7 Correct 5 ms 1628 KB Ok
8 Correct 78 ms 5372 KB Ok
9 Correct 37 ms 3660 KB Ok
10 Correct 1 ms 1372 KB Ok
11 Correct 2 ms 1536 KB Ok
12 Correct 18 ms 2268 KB Ok
13 Correct 1 ms 1368 KB Ok
14 Correct 168 ms 9524 KB Ok
15 Correct 167 ms 9696 KB Ok
16 Correct 165 ms 9412 KB Ok
17 Correct 79 ms 5460 KB Ok
18 Correct 78 ms 5456 KB Ok
19 Correct 39 ms 3436 KB Ok
20 Correct 37 ms 3408 KB Ok
21 Correct 19 ms 2268 KB Ok
22 Correct 19 ms 2400 KB Ok
23 Correct 10 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 186 ms 9584 KB Ok
28 Correct 86 ms 5296 KB Ok
29 Correct 175 ms 9920 KB Ok
30 Correct 10 ms 1880 KB Ok
31 Correct 1 ms 1368 KB Ok
32 Correct 5 ms 1628 KB Ok
33 Correct 20 ms 2392 KB Ok
34 Correct 1 ms 1624 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 5356 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5488 KB Ok
2 Correct 206 ms 9708 KB Ok
3 Correct 172 ms 9556 KB Ok
4 Correct 10 ms 1884 KB Ok
5 Correct 1 ms 1372 KB Ok
6 Correct 20 ms 2392 KB Ok
7 Correct 164 ms 9552 KB Ok
8 Correct 2 ms 1368 KB Ok
9 Correct 1 ms 1372 KB Ok
10 Correct 1 ms 1372 KB Ok
11 Correct 42 ms 3420 KB Ok
12 Correct 86 ms 5464 KB Ok