oj.uz

Submission #155685

# Submission time Handle Problem Language Result Execution time Memory
155685 2019-09-29T19:36:26 Z qkxwsm "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 280 ms 6472 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 300013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K;
bool T;
int st;
int ans[MAXN];
vi arr;
bitset<MAXN> vis;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> T;
	string temps; cin >> temps;
	reverse(ALL(temps));
	while(SZ(temps) < N)
	{
		temps += '0';
	}
	reverse(ALL(temps));
	FOR(i, 0, N)
	{
		st *= 2; st += (temps[i] == '1');
	}
	//find N linearly independent vectors
	vis[0] = true;
	FOR(i, 0, (1 << N))
	{
		if (__builtin_popcount(i) != K) continue;
		if (vis[i]) continue;
		arr.PB(i);
		FOR(j, 0, (1 << N))
		{
			if (vis[j] || vis[j ^ i])
			{
				vis[j] = true;
				vis[i] = true;
			}
		}
	}
	if (SZ(arr) != N)
	{
		cout << "-1\n";
		return 0;
	}
	// cerr << "HEY\n";
	FOR(i, 1, (1 << N))
	{
		ans[i] = __builtin_ctz(i);
	}
	FOR(i, 1, (1 << N))
	{
		ans[i] = arr[ans[i]];
	}
	// FOR(i, 0, N)
	// {
	// 	cerr << arr[i] << ' ';
	// }
	// cerr << endl;
	ans[0] = st;
	FOR(i, 1, (1 << N))
	{
		ans[i] ^= ans[i - 1];
	}
	vis.reset();
	FOR(i, 0, (1 << N))
	{
		if (vis[ans[i]])
		{
			cout << "-1\n";
			return 0;
		}
		assert(!vis[ans[i]]);
		// cerr << ans[i] << ' ';
		vis[ans[i]] = true;
	}
	// cerr << endl;
	cout << (1 << N) << '\n';
	FOR(i, 0, (1 << N))
	{
		FORD(j, N, 0)
		{
			cout << ((ans[i] & (1 << j)) ? 1 : 0);
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 14 ms 376 KB Ok
3 Correct 8 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 8 ms 376 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 6472 KB Ok
2 Correct 116 ms 3192 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 7 ms 504 KB Ok
3 Correct 122 ms 3192 KB Ok
4 Correct 56 ms 1784 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 27 ms 1016 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 6360 KB Ok
2 Correct 245 ms 6392 KB Ok
3 Correct 248 ms 6336 KB Ok
4 Correct 118 ms 3220 KB Ok
5 Correct 117 ms 3192 KB Ok
6 Correct 59 ms 1784 KB Ok
7 Correct 57 ms 1784 KB Ok
8 Correct 29 ms 1016 KB Ok
9 Correct 28 ms 1016 KB Ok
10 Correct 15 ms 760 KB Ok
11 Correct 7 ms 376 KB Ok
12 Correct 3 ms 376 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 6472 KB Ok
2 Correct 116 ms 3192 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 7 ms 504 KB Ok
8 Correct 122 ms 3192 KB Ok
9 Correct 56 ms 1784 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 27 ms 1016 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 247 ms 6360 KB Ok
15 Correct 245 ms 6392 KB Ok
16 Correct 248 ms 6336 KB Ok
17 Correct 118 ms 3220 KB Ok
18 Correct 117 ms 3192 KB Ok
19 Correct 59 ms 1784 KB Ok
20 Correct 57 ms 1784 KB Ok
21 Correct 29 ms 1016 KB Ok
22 Correct 28 ms 1016 KB Ok
23 Correct 15 ms 760 KB Ok
24 Correct 7 ms 376 KB Ok
25 Correct 3 ms 376 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 280 ms 6376 KB Ok
28 Correct 126 ms 3320 KB Ok
29 Correct 256 ms 6392 KB Ok
30 Correct 14 ms 632 KB Ok
31 Correct 3 ms 376 KB Ok
32 Correct 8 ms 504 KB Ok
33 Correct 28 ms 1056 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 123 ms 3320 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3268 KB Ok
2 Correct 253 ms 6416 KB Ok
3 Correct 246 ms 6392 KB Ok
4 Correct 14 ms 760 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 28 ms 1016 KB Ok
7 Correct 245 ms 6392 KB Ok
8 Correct 2 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 58 ms 1784 KB Ok
12 Correct 118 ms 3320 KB Ok