oj.uz

Submission #166808

# Submission time Handle Problem Language Result Execution time Memory
166808 2019-12-04T07:20:01 Z Yaroslaff "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 268 ms 6520 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 15 ms 376 KB Ok
3 Correct 8 ms 380 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 380 KB Ok
6 Correct 2 ms 424 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 250 ms 6480 KB Ok
2 Correct 118 ms 3436 KB Ok
3 Correct 3 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 8 ms 504 KB Ok
3 Correct 118 ms 3244 KB Ok
4 Correct 57 ms 1800 KB Ok
5 Correct 3 ms 504 KB Ok
6 Correct 3 ms 504 KB Ok
7 Correct 28 ms 1020 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 6516 KB Ok
2 Correct 246 ms 6392 KB Ok
3 Correct 251 ms 6380 KB Ok
4 Correct 119 ms 3320 KB Ok
5 Correct 118 ms 3280 KB Ok
6 Correct 57 ms 1784 KB Ok
7 Correct 57 ms 1788 KB Ok
8 Correct 28 ms 1016 KB Ok
9 Correct 28 ms 988 KB Ok
10 Correct 14 ms 760 KB Ok
11 Correct 2 ms 376 KB Ok
12 Correct 3 ms 380 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 6480 KB Ok
2 Correct 118 ms 3436 KB Ok
3 Correct 3 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 8 ms 504 KB Ok
8 Correct 118 ms 3244 KB Ok
9 Correct 57 ms 1800 KB Ok
10 Correct 3 ms 504 KB Ok
11 Correct 3 ms 504 KB Ok
12 Correct 28 ms 1020 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 247 ms 6516 KB Ok
15 Correct 246 ms 6392 KB Ok
16 Correct 251 ms 6380 KB Ok
17 Correct 119 ms 3320 KB Ok
18 Correct 118 ms 3280 KB Ok
19 Correct 57 ms 1784 KB Ok
20 Correct 57 ms 1788 KB Ok
21 Correct 28 ms 1016 KB Ok
22 Correct 28 ms 988 KB Ok
23 Correct 14 ms 760 KB Ok
24 Correct 2 ms 376 KB Ok
25 Correct 3 ms 380 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 253 ms 6392 KB Ok
28 Correct 119 ms 3320 KB Ok
29 Correct 249 ms 6392 KB Ok
30 Correct 15 ms 632 KB Ok
31 Correct 3 ms 504 KB Ok
32 Correct 8 ms 504 KB Ok
33 Correct 29 ms 1272 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 122 ms 3292 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 3336 KB Ok
2 Correct 261 ms 6392 KB Ok
3 Correct 250 ms 6520 KB Ok
4 Correct 15 ms 760 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 29 ms 1016 KB Ok
7 Correct 268 ms 6392 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 60 ms 1784 KB Ok
12 Correct 120 ms 3248 KB Ok