oj.uz

Submission #288061

# Submission time Handle Problem Language Result Execution time Memory
288061 2020-09-01T08:23:14 Z dvdg6566 "The Lyuboyn" code (IZhO19_lyuboyn) C++14
52 / 100
 87 ms 9576 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
const int MAXN=1001000;
const ll MOD=998244353;

int N,K,T;
string S;

void tobin(int y,int len){
	string x;
	while(y){
		x+=('0' + y%2);
		y/=2;
	}
	while(SZ(x) < len)x+='0';
	reverse(ALL(x));
	cout<<x;
}

vi A;
vi B;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>K>>T>>S;
	if(K%2==0){
		cout<<-1;
		return 0;
	}

	ll flip=0;
	if(K*2>N){
		K=N-K;
		flip=1;
	}

	ll v=0;ll k=1;
	while(SZ(S)){
		if(S.back() == '1')v+=k;
		k*=2;
		S.pop_back();
	}
	ll mod=(1<<(N-K+1));

	// cerr<<mod<<'\n';

	A.pb(v%(1<<(K-1)));

	B.pb(v/(1<<(K-1)));

	ll alen=(K-1);
	for(int i=1;i<=(1<<alen);++i){
		for(int j=0;j<mod-1;++j){
			A.pb(A.back() ^ ((1<<alen)-1));
		}
		// flip A back
		if(SZ(A) < (1<<N))A.pb(A.back() ^ (i&(-i)));
	}

	for(int i=1;i<=(1<<alen);++i){
		for(int j=1;j<mod;++j){
			B.pb(B.back() ^ (j&(-j)));
		}
		// flip A back
		if(SZ(B) < (1<<N))B.pb(B.back() ^ ((1<<(K-1))-1));
	}

	cout<<(1<<N)<<'\n';

	for(int i=0;i<SZ(A);++i){
		if(flip&&i%2){
			A[i]=((1<<(K-1))-1)^A[i];
			B[i]=((1<<(N-K+1))-1)^B[i];
		}
		tobin(B[i],(N-K+1));
		tobin(A[i],K-1);
		cout<<'\n';
	}
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9576 KB Ok
2 Correct 41 ms 4848 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 0 ms 384 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Ok
2 Correct 3 ms 640 KB Ok
3 Correct 34 ms 4844 KB Ok
4 Correct 17 ms 2684 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 8 ms 1532 KB Ok
8 Correct 0 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9564 KB Ok
2 Correct 69 ms 9572 KB Ok
3 Correct 84 ms 9572 KB Ok
4 Correct 44 ms 4844 KB Ok
5 Correct 36 ms 4848 KB Ok
6 Correct 17 ms 2684 KB Ok
7 Correct 20 ms 2676 KB Ok
8 Correct 11 ms 1532 KB Ok
9 Correct 8 ms 1532 KB Ok
10 Correct 4 ms 1024 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 384 KB Ok
13 Correct 1 ms 384 KB Ok

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9576 KB Ok
2 Correct 41 ms 4848 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 0 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 3 ms 640 KB Ok
8 Correct 34 ms 4844 KB Ok
9 Correct 17 ms 2684 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 8 ms 1532 KB Ok
13 Correct 0 ms 384 KB Ok
14 Correct 70 ms 9564 KB Ok
15 Correct 69 ms 9572 KB Ok
16 Correct 84 ms 9572 KB Ok
17 Correct 44 ms 4844 KB Ok
18 Correct 36 ms 4848 KB Ok
19 Correct 17 ms 2684 KB Ok
20 Correct 20 ms 2676 KB Ok
21 Correct 11 ms 1532 KB Ok
22 Correct 8 ms 1532 KB Ok
23 Correct 4 ms 1024 KB Ok
24 Correct 1 ms 384 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 87 ms 9544 KB Ok
28 Incorrect 36 ms 4844 KB The values in the output sequence are not pairwise distinct!
29 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

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