oj.uz

Submission #357589

# Submission time Handle Problem Language Result Execution time Memory
357589 2021-01-24T08:12:43 Z kshitij_sodani "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 669 ms 66492 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n,k,t;
vector<vector<int>> ans;
vector<vector<int>> solve(int n){
	if(n==1){
		return {{0},{1}};
		return {{0,0},{0,1},{1,1},{1,0}};
	}
	else{
		vector<vector<int>> aa=solve(n-1);
		vector<vector<int>> bb=solve(n-1);
		reverse(bb.begin(),bb.end());
		for(int i=0;i<aa.size();i++){
			aa[i].pb(0);
			bb[i].pb(1);
		}
		for(int i=0;i<bb.size();i++){
			aa.pb(bb[i]);
		}
		return aa;
	}
}
int it[20];
vector<vector<int>> solve2(int n){
	if(n==k+1){
		return ans;
	}
	else{
		vector<vector<int>> aa=solve2(n-1);
		vector<vector<int>> cur;
		for(int i=0;i<aa.size();i++){
			cur.pb(aa[i]);
			cur[i].pb(0);
		}
		int ind=-1;
		for(int j=0;j<n-1;j++){
			if(aa.back()[j]==1){
				ind=j;
				break;
			}
		}
		for(int i=0;i<aa.size();i++){
			vector<int> dd;
			for(int j=0;j<aa[i].size();j++){
				if(j==ind){
					dd.pb(aa[i][j]^1);
				}
				else{
					dd.pb(aa[i][j]);
				}
			}
			dd.pb(1);
			cur.pb(dd);
		}
		return cur;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>t;
	string s;
	cin>>s;
	if(k%2==0){
		cout<<-1<<endl;
		return 0;
	}
/*	int cur=0;
	for(int i=0;i<(1<<n);i++){
		if(__builtin_popcount(i)==k){
			cur^=i;
			for(auto j=0;j<n;j++){
				if(cur&(1<<j)){
					cout<<1;
				}
				else{
					cout<<0;
				}
			}
			cout<<endl;
		}
	}
	return 0;
*/


	for(int i=0;i<n;i++){
		it[i]=s[i]-'0';
	}

	//if(k==1 or k==n-1){
		ans=solve(k+1);
		for(int i=1;i<(ans.size());i+=2){
			for(int j=0;j<k+1;j++){
				ans[i][j]^=1;
			}
		}
		cout<<(1<<n)<<endl;
		vector<vector<int>> ans2=solve2(n);
		for(auto j:ans2){
			for(int ii=0;ii<n;ii++){
				cout<<(j[ii]^it[ii]);
			}
			cout<<endl;
		}
		/*int ind=-1;
		int kk=0;
		if(k==n-1){
			kk=1;
		}
		for(int i=0;i<ans.size();i++){
			int st=1;
			for(int j=0;j<n;j++){
				if(ans[i][j]!=it[j]){
					st=0;
				}
			}
			if(st==1){
				ind=i;
			}
		}
		cout<<ans.size()<<endl;
	//	int cot=0;
		int cot=0;
		for(auto j:ans){
			for(int i=0;i<n;i++){
				if(cot==1 and kk==1){
					cout<<((it[i]^j[i])^1);
					continue;
				}
				cout<<(it[i]^j[i]);
			}
			cout<<endl;
			cot=1-cot;
		}*/
	//}
	
 
	return 0;
}

Compilation message

lyuboyn.cpp: In function 'std::vector<std::vector<int> > solve(int)':
lyuboyn.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i=0;i<aa.size();i++){
      |               ~^~~~~~~~~~
lyuboyn.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i=0;i<bb.size();i++){
      |               ~^~~~~~~~~~
lyuboyn.cpp: In function 'std::vector<std::vector<int> > solve2(int)':
lyuboyn.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0;i<aa.size();i++){
      |               ~^~~~~~~~~~
lyuboyn.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<aa.size();i++){
      |               ~^~~~~~~~~~
lyuboyn.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int j=0;j<aa[i].size();j++){
      |                ~^~~~~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i=1;i<(ans.size());i+=2){
      |               ~^~~~~~~~~~~~~

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 0 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 1 ms 384 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 1 ms 364 KB Ok
7 Correct 1 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 402 ms 54552 KB Ok
2 Correct 194 ms 26828 KB Ok
3 Correct 2 ms 492 KB Ok
4 Correct 1 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 10 ms 1772 KB Ok
3 Correct 193 ms 26972 KB Ok
4 Correct 92 ms 13012 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 3 ms 620 KB Ok
7 Correct 44 ms 6364 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 54716 KB Ok
2 Correct 404 ms 54588 KB Ok
3 Correct 403 ms 54588 KB Ok
4 Correct 188 ms 26828 KB Ok
5 Correct 192 ms 26940 KB Ok
6 Correct 90 ms 13012 KB Ok
7 Correct 90 ms 13012 KB Ok
8 Correct 43 ms 6364 KB Ok
9 Correct 43 ms 6364 KB Ok
10 Correct 21 ms 3044 KB Ok
11 Correct 2 ms 492 KB Ok
12 Correct 2 ms 512 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 54552 KB Ok
2 Correct 194 ms 26828 KB Ok
3 Correct 2 ms 492 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 10 ms 1772 KB Ok
8 Correct 193 ms 26972 KB Ok
9 Correct 92 ms 13012 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 3 ms 620 KB Ok
12 Correct 44 ms 6364 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 403 ms 54716 KB Ok
15 Correct 404 ms 54588 KB Ok
16 Correct 403 ms 54588 KB Ok
17 Correct 188 ms 26828 KB Ok
18 Correct 192 ms 26940 KB Ok
19 Correct 90 ms 13012 KB Ok
20 Correct 90 ms 13012 KB Ok
21 Correct 43 ms 6364 KB Ok
22 Correct 43 ms 6364 KB Ok
23 Correct 21 ms 3044 KB Ok
24 Correct 2 ms 492 KB Ok
25 Correct 2 ms 512 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 666 ms 66364 KB Ok
28 Correct 205 ms 28616 KB Ok
29 Correct 404 ms 54972 KB Ok
30 Correct 21 ms 3172 KB Ok
31 Correct 2 ms 492 KB Ok
32 Correct 13 ms 2284 KB Ok
33 Correct 60 ms 7772 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 492 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 254 ms 33356 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 33536 KB Ok
2 Correct 669 ms 66492 KB Ok
3 Correct 410 ms 54968 KB Ok
4 Correct 26 ms 3172 KB Ok
5 Correct 1 ms 492 KB Ok
6 Correct 56 ms 7772 KB Ok
7 Correct 412 ms 54588 KB Ok
8 Correct 2 ms 492 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 2 ms 492 KB Ok
11 Correct 154 ms 16212 KB Ok
12 Correct 205 ms 28616 KB Ok