oj.uz

Submission #370490

# Submission time Handle Problem Language Result Execution time Memory
370490 2021-02-24T04:32:06 Z fhvirus "The Lyuboyn" code (IZhO19_lyuboyn) C++17
52 / 100
 264 ms 7648 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(vector<int> v){
	int n = __lg(v.size());
	cout << v.size() << '\n';
	for(auto i: v){
		for(int j = n - 1; j >= 0; --j)
			cout << ((i & (1<<j)) ? 1 : 0);
		cout << '\n';
	}
}
vector<int> solvek1(int n){
	vector<int> 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 ans;
}
vector<int> addk(int k, int n, vector<int> v){
	if(k == 0) return v;
	vector<int> h = solvek1(k);
	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);
		}
	}
	return ans;
}
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 or k >= n){
		puts("-1");
		return 0;
	}
	vector<int> ans = solvek1(n - k + 1);
	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(ans);
	return 0;
}

Compilation message

lyuboyn.cpp: In function 'std::vector<int> 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:48:2: note: in expansion of macro 'FOR'
   48 |  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:49:3: note: in expansion of macro 'FOR'
   49 |   FOR(x, v.size()){
      |   ^~~
lyuboyn.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    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: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:79:2: note: in expansion of macro 'FOR'
   79 |  FOR(i,ans.size()) if(ans[i] == s){
      |  ^~~

Subtask #1
0.0 / 0.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 7380 KB Ok
2 Correct 125 ms 3808 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 124 ms 4192 KB Ok
4 Correct 62 ms 2024 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 364 KB Ok
7 Correct 30 ms 1196 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 7648 KB Ok
2 Correct 262 ms 7648 KB Ok
3 Correct 264 ms 7564 KB Ok
4 Correct 127 ms 3944 KB Ok
5 Correct 126 ms 4196 KB Ok
6 Correct 60 ms 2196 KB Ok
7 Correct 59 ms 2024 KB Ok
8 Correct 29 ms 1196 KB Ok
9 Correct 29 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
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 7380 KB Ok
2 Correct 125 ms 3808 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 124 ms 4192 KB Ok
9 Correct 62 ms 2024 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 364 KB Ok
12 Correct 30 ms 1196 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 264 ms 7648 KB Ok
15 Correct 262 ms 7648 KB Ok
16 Correct 264 ms 7564 KB Ok
17 Correct 127 ms 3944 KB Ok
18 Correct 126 ms 4196 KB Ok
19 Correct 60 ms 2196 KB Ok
20 Correct 59 ms 2024 KB Ok
21 Correct 29 ms 1196 KB Ok
22 Correct 29 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 Runtime error 4 ms 2400 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 3940 KB The values in the output sequence are not pairwise distinct!
2 Halted 0 ms 0 KB -