oj.uz

Submission #328594

# Submission time Handle Problem Language Result Execution time Memory
328594 2020-11-17T09:15:27 Z ryansee "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 76 ms 7640 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
ll n, k, t, s;
int main() {
	FAST
	cin>>n>>k>>t;
	if(k%2==0) { cout<<"-1\n"; return 0; }
	assert(k&1);
	FOR(i,1,n) {
		char ch;cin>>ch;
		s<<=1,s|=(ch&15);
	}
	function<vector<ll>(ll,ll)>dp=[&](ll n,ll k){
		assert(n>=1);
		if(k==1) {
			if(n==1) return vector<ll>{0,1};
			else {
				vector<ll> v;
				vector<ll> ret = dp(n-1, k);
				for(auto i:ret) v.eb(i<<1);
				while(ret.size()) v.eb(ret.back()<<1|1), ret.pop_back();
				return v;
			}
		}
		vector<ll> ret = dp(n-2, k-2);
		vector<ll> v;
		FOR(i,0,siz(ret)-1) if(i%2==0) v.eb(ret[i]<<2); else v.eb(ret[i]<<2|3);
		ll bit = -1;
		FOR(i,0,17) if((1<<i&ret[0]) == (1<<i&ret.back())) { bit = i; break; }
		assert(~bit);
		FOR(i,0,siz(ret)-1) if(i%2==0) v.eb(((ret[i]^(1<<bit))<<2)|1); else v.eb(((ret[i]^(1<<bit))<<2)|2);
		FOR(i,0,siz(ret)-1) if(i%2==0) v.eb(ret[i]<<2|3); else v.eb(ret[i]<<2);
		FOR(i,0,siz(ret)-1) if(i%2==0) v.eb(((ret[i]^(1<<bit))<<2)|2); else v.eb(((ret[i]^(1<<bit))<<2)|1);
		return v;
	};
	vector<ll> v = dp(n, k);
	ll change = 0;
	FOR(i,0,n-1) if((1<<i&v[0]) != (1<<i&s)) change|=1<<i;
	for(auto&i:v) i^=change;
	auto b=[&](ll x){
		string s;
		DEC(i,n-1,0) if(1<<i&x) s += '1'; else s += '0';
		return s;
	};
	cout<<(1<<n)<<'\n';
	for(auto i:v) cout<<b(i)<<'\n';
}

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 384 KB Ok
2 Correct 0 ms 364 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 0 ms 364 KB Ok
7 Correct 0 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 71 ms 7632 KB Ok
2 Correct 35 ms 3928 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 3 ms 620 KB Ok
3 Correct 36 ms 3932 KB Ok
4 Correct 18 ms 2168 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 8 ms 1384 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7576 KB Ok
2 Correct 75 ms 7640 KB Ok
3 Correct 72 ms 7508 KB Ok
4 Correct 43 ms 3840 KB Ok
5 Correct 35 ms 3932 KB Ok
6 Correct 18 ms 2084 KB Ok
7 Correct 18 ms 2144 KB Ok
8 Correct 8 ms 1384 KB Ok
9 Correct 8 ms 1300 KB Ok
10 Correct 6 ms 832 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 71 ms 7632 KB Ok
2 Correct 35 ms 3928 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 3 ms 620 KB Ok
8 Correct 36 ms 3932 KB Ok
9 Correct 18 ms 2168 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 8 ms 1384 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 76 ms 7576 KB Ok
15 Correct 75 ms 7640 KB Ok
16 Correct 72 ms 7508 KB Ok
17 Correct 43 ms 3840 KB Ok
18 Correct 35 ms 3932 KB Ok
19 Correct 18 ms 2084 KB Ok
20 Correct 18 ms 2144 KB Ok
21 Correct 8 ms 1384 KB Ok
22 Correct 8 ms 1300 KB Ok
23 Correct 6 ms 832 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 74 ms 7472 KB Ok
28 Correct 35 ms 3856 KB Ok
29 Correct 71 ms 7596 KB Ok
30 Correct 4 ms 836 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 2 ms 620 KB Ok
33 Correct 9 ms 1304 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 35 ms 3856 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3984 KB Ok
2 Correct 72 ms 7600 KB Ok
3 Correct 73 ms 7596 KB Ok
4 Correct 4 ms 836 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 8 ms 1304 KB Ok
7 Correct 71 ms 7512 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 18 ms 2176 KB Ok
12 Correct 35 ms 3860 KB Ok