oj.uz

Submission #370544

# Submission time Handle Problem Language Result Execution time Memory
370544 2021-02-24T05:51:46 Z Kevin_Zhang_TW "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 282 ms 7812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV 
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 18, MAX_M = 1<<MAX_N;

int N, K, T, S;
int nxt[MAX_M];

void ob(int x) {
	for (int i = N-1;i >= 0;--i)
		cout << (x>>i&1);
	cout << '\n';
}

vector<int> xo;
void divcons(int N, int f = 0) {
	static int lst[MAX_M];
	if (N == 0) {
		nxt[f] = f^1;
		nxt[f^1] = f;
		return;
	}
	divcons(N-1, f);
	divcons(N-1,f|(1<<N));

	for (int i = 0;i < (1<<(N));++i)
		lst[ nxt[f|i] ] = f|i;
	for (int i = 0;i < (1<<(N));++i)
		nxt[f|i] = lst[f|i];

	int X = f, Y = f|(1<<N);
	for (int i = 1;i < 1<<N;++i) {
		X = nxt[X];
		Y = nxt[Y];
	}
	DE(N, f, X);

	nxt[f|(1<<N)] = f;
	nxt[X] = X|(1<<N);


}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K >> T;
	{
		string v;
		cin >> v;
		DE(v);
		for (char i : v) 
			S = (S<<1) | (i-'0');
		DE(S);
	}

	if (K == 1 && T == 1) {
		divcons(N-1);
		cout << (1<<N) << '\n';
		for (int i = 0, x = S;i < 1<<N;++i) 
			ob(x), x = nxt[x];
		return 0;
	}

	for (int i = 0;i < 1<<N;++i)
		if (__builtin_popcount(i) == K)
			xo.pb(i);

	vector<int> per;

	srand(time(0));

	random_shuffle(AI(xo));

	int ind = 0;

	vector<int> vis(1<<N);
	for (int i = 0, x = 0;i < 1<<N;++i) {
		per.pb(x);
		vis[x] = true;
		for (int u : xo) 
			if (!vis[x ^ u]) {
				x ^= u;
				break;
			}
		if (x == per.back()) break;
	}

	if (per.size() != (1<<N)) return puts("-1"), 0;

	DE(per.size(), 1<<N);
	debug(AI(per));


	cout << per.size() << '\n';
	for (int u : per)
		ob(u ^ S);
}

Compilation message

lyuboyn.cpp: In function 'void divcons(int, int)':
lyuboyn.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
lyuboyn.cpp:50:2: note: in expansion of macro 'DE'
   50 |  DE(N, f, X);
      |  ^~
lyuboyn.cpp: In function 'int32_t main()':
lyuboyn.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
lyuboyn.cpp:63:3: note: in expansion of macro 'DE'
   63 |   DE(v);
      |   ^~
lyuboyn.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
lyuboyn.cpp:66:3: note: in expansion of macro 'DE'
   66 |   DE(S);
      |   ^~
lyuboyn.cpp:101:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |  if (per.size() != (1<<N)) return puts("-1"), 0;
      |      ~~~~~~~~~~~^~~~~~~~~
lyuboyn.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
lyuboyn.cpp:103:2: note: in expansion of macro 'DE'
  103 |  DE(per.size(), 1<<N);
      |  ^~
lyuboyn.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
lyuboyn.cpp:104:2: note: in expansion of macro 'debug'
  104 |  debug(AI(per));
      |  ^~~~~
lyuboyn.cpp:87:6: warning: unused variable 'ind' [-Wunused-variable]
   87 |  int ind = 0;
      |      ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 4 ms 2032 KB Ok
3 Correct 3 ms 1388 KB Ok
4 Correct 0 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 3 ms 1292 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 7404 KB Ok
2 Correct 131 ms 3692 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 492 KB Ok
5 Correct 1 ms 364 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 7 ms 620 KB Ok
3 Correct 130 ms 3948 KB Ok
4 Correct 61 ms 2160 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 364 KB Ok
7 Correct 29 ms 1260 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 7688 KB Ok
2 Correct 270 ms 7776 KB Ok
3 Correct 272 ms 7656 KB Ok
4 Correct 132 ms 4004 KB Ok
5 Correct 126 ms 3948 KB Ok
6 Correct 60 ms 2316 KB Ok
7 Correct 65 ms 2160 KB Ok
8 Correct 29 ms 1260 KB Ok
9 Correct 31 ms 1388 KB Ok
10 Correct 15 ms 876 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 7404 KB Ok
2 Correct 131 ms 3692 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 492 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 7 ms 620 KB Ok
8 Correct 130 ms 3948 KB Ok
9 Correct 61 ms 2160 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 364 KB Ok
12 Correct 29 ms 1260 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 267 ms 7688 KB Ok
15 Correct 270 ms 7776 KB Ok
16 Correct 272 ms 7656 KB Ok
17 Correct 132 ms 4004 KB Ok
18 Correct 126 ms 3948 KB Ok
19 Correct 60 ms 2316 KB Ok
20 Correct 65 ms 2160 KB Ok
21 Correct 29 ms 1260 KB Ok
22 Correct 31 ms 1388 KB Ok
23 Correct 15 ms 876 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 268 ms 7812 KB Ok
28 Correct 143 ms 3992 KB Ok
29 Correct 273 ms 7612 KB Ok
30 Correct 14 ms 748 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 7 ms 620 KB Ok
33 Correct 29 ms 1260 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 492 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 133 ms 3948 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3948 KB Ok
2 Correct 267 ms 7528 KB Ok
3 Correct 281 ms 7776 KB Ok
4 Correct 14 ms 748 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 30 ms 1260 KB Ok
7 Correct 271 ms 7520 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 62 ms 2160 KB Ok
12 Correct 128 ms 3960 KB Ok