oj.uz

Submission #370514

# Submission time Handle Problem Language Result Execution time Memory
370514 2021-02-24T04:57:35 Z fhvirus "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 304 ms 7676 KB 
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) (x).begin(),(x).end()
template<typename I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<typename I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr << endl;}
template<typename I, typename...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<typename I> void DE(I a, I b){ while(a < b) cerr<<*a<<" \n"[next(a)==b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif

void printb(int n, vector<int> v){
	cout << v.size() << '\n';
	for(auto i: v){
		for(int j = n - 1; j >= 0; --j)
			cout << ((i & (1<<j)) ? 1 : 0);
		cout << '\n';
	}
}
void solvek1(int n, vector<int> & ans){
	ans = {0, 1};
	FOO(i,2,n){
		vector<int> b = ans;
		reverse(AI(b));
		for(auto &j: b) j += (1<<(i-1));
		for(auto j: b) ans.pb(j);
	}
	return;
}
void addk(int k, int n, vector<int>& v){
	if(k <= 0) return;
	vector<int> h; solvek1(k, h);
	vector<int> ans;
	int msk = (((1<<k)-1) << n);
	FOR(st, h.size()){
		FOR(x, v.size()){
			int id = st + x; if(id >= v.size()) id %= v.size();
			int i = v[id];
			i ^= (h[st]<<n);
			if(x & 1) i ^= msk;
			ans.pb(i);
		}
	}
	ans.swap(v);
	return;
}
int tobin(string s){
	int ans = 0;
	for(int i = 0; i < s.size(); ++i)
		if(s[s.size() - 1 - i] == '1')
			ans += (1<<i);
	return ans;
}
int n, k, t;
string ss;

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k >> t >> ss;
	if(k % 2 == 0){
		puts("-1");
		return 0;
	}

	vector<int> ans;
	solvek1(n - k + 1, ans);
	DE(AI(ans));

	addk(k - 1, n - k + 1, ans);

	int s = tobin(ss);
	FOR(i,ans.size())if(ans[i] == s){
		rotate(ans.begin(), ans.begin() + i, ans.end());
		break;
	}
	
	printb(n, ans);

	return 0;
}

Compilation message

lyuboyn.cpp: In function 'void addk(int, int, std::vector<int>&)':
lyuboyn.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
lyuboyn.cpp:47:2: note: in expansion of macro 'FOR'
   47 |  FOR(st, h.size()){
      |  ^~~
lyuboyn.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
lyuboyn.cpp:48:3: note: in expansion of macro 'FOR'
   48 |   FOR(x, v.size()){
      |   ^~~
lyuboyn.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    int id = st + x; if(id >= v.size()) id %= v.size();
      |                        ~~~^~~~~~~~~~~
lyuboyn.cpp: In function 'int tobin(std::string)':
lyuboyn.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < s.size(); ++i)
      |                 ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int32_t main()':
lyuboyn.cpp:21:17: warning: statement has no effect [-Wunused-value]
   21 | #define DE(...) 0
      |                 ^
lyuboyn.cpp:79:2: note: in expansion of macro 'DE'
   79 |  DE(AI(ans));
      |  ^~
lyuboyn.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
lyuboyn.cpp:84:2: note: in expansion of macro 'FOR'
   84 |  FOR(i,ans.size())if(ans[i] == s){
      |  ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 364 KB Ok
3 Correct 0 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 0 ms 364 KB Ok
6 Correct 0 ms 364 KB Ok
7 Correct 0 ms 364 KB Ok
8 Correct 0 ms 364 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 7676 KB Ok
2 Correct 134 ms 3832 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 0 ms 364 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 492 KB Ok
3 Correct 130 ms 4068 KB Ok
4 Correct 61 ms 2024 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 364 KB Ok
7 Correct 29 ms 1228 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 7540 KB Ok
2 Correct 304 ms 7648 KB Ok
3 Correct 274 ms 7644 KB Ok
4 Correct 129 ms 3952 KB Ok
5 Correct 128 ms 4068 KB Ok
6 Correct 61 ms 2268 KB Ok
7 Correct 61 ms 2156 KB Ok
8 Correct 31 ms 1100 KB Ok
9 Correct 30 ms 1132 KB Ok
10 Correct 14 ms 748 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 276 ms 7676 KB Ok
2 Correct 134 ms 3832 KB Ok
3 Correct 1 ms 364 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 7 ms 492 KB Ok
8 Correct 130 ms 4068 KB Ok
9 Correct 61 ms 2024 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 364 KB Ok
12 Correct 29 ms 1228 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 270 ms 7540 KB Ok
15 Correct 304 ms 7648 KB Ok
16 Correct 274 ms 7644 KB Ok
17 Correct 129 ms 3952 KB Ok
18 Correct 128 ms 4068 KB Ok
19 Correct 61 ms 2268 KB Ok
20 Correct 61 ms 2156 KB Ok
21 Correct 31 ms 1100 KB Ok
22 Correct 30 ms 1132 KB Ok
23 Correct 14 ms 748 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 275 ms 7516 KB Ok
28 Correct 129 ms 3960 KB Ok
29 Correct 273 ms 7528 KB Ok
30 Correct 14 ms 748 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 7 ms 492 KB Ok
33 Correct 31 ms 1132 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 131 ms 3940 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4068 KB Ok
2 Correct 277 ms 7536 KB Ok
3 Correct 271 ms 7528 KB Ok
4 Correct 14 ms 748 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 29 ms 1132 KB Ok
7 Correct 270 ms 7648 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 2024 KB Ok
12 Correct 129 ms 3960 KB Ok