oj.uz

Submission #336530

# Submission time Handle Problem Language Result Execution time Memory
336530 2020-12-15T14:11:51 Z Kerim "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 508 ms 7756 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int N,K,T;
char S[22];
void print(int x){
	for(int i=0;i<N;i++)
		printf("%d",(x>>i&1));	
	puts("");
}
bool checker(vector<int>v){
	int sz=int(v.size());
	assert(sz==(1<<N));
	for(int i=0;i<sz;i++)
		if(__builtin_popcount(v[i]^v[(i+1)%sz])!=K)
			return 0;
	return 1;	
}
vector<int>rec(int n,int k){
	if(k==1){
		if(n==1){
			vector<int>tmp;
			tmp.pb(0);tmp.pb(1);
			return tmp;	
		}
		vector<int>tmp=rec(n-1,k),ans;
		tr(it,tmp)
			ans.pb((*it)*2);
		reverse(all(tmp));
		tr(it,tmp)
			ans.pb((*it)*2+1);
		return ans;
	}
	vector<int>A=rec(n-2,k-2);int sz=(1<<(n-2));
	vector<int>B=A,ans;reverse(all(B));
	for(int i=0;i<sz;i++){
		int cur=A[i];
		if(i%2==0)
			ans.pb(cur*4);
		else
			ans.pb(cur*4+3);
	}	
	for(int i=0;i<sz;i++){
		int cur=B[i]^((1<<(k-1))-1);
		if(i%2==0)
			ans.pb(cur*4+1);
		else
			ans.pb(cur*4+2);
	}
	for(int i=0;i<sz;i++){
		int cur=A[i];
		if(i%2==0)
			ans.pb(cur*4+3);
		else
			ans.pb(cur*4);
	}	
	for(int i=0;i<sz;i++){
		int cur=B[i]^((1<<(k-1))-1);
		if(i%2==0)
			ans.pb(cur*4+2);
		else
			ans.pb(cur*4+1);
	}
	return ans;
}
int main(){
   // freopen("file.in", "r", stdin);
    scanf("%d%d%d",&N,&K,&T);
    scanf("%s",S);
    if(K%2==0)
    	return 0*puts("-1");
    int res=0;
    for(int i=0;i<N;i++)
    	if(S[i]=='1')
    		res+=(1<<i);
    vector<int>ans=rec(N,K);
    vector<int>barla;
    tr(it,ans)
    	barla.pb(*it^res);
    printf("%d\n",(1<<N));
    tr(it,ans)
    	print(*it^res);
    //assert(checker(barla));
	return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d%d%d",&N,&K,&T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
lyuboyn.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%s",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 1 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 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 0 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 508 ms 7756 KB Ok
2 Correct 236 ms 3800 KB Ok
3 Correct 2 ms 364 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 12 ms 492 KB Ok
3 Correct 238 ms 3876 KB Ok
4 Correct 125 ms 2116 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 3 ms 364 KB Ok
7 Correct 53 ms 1388 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 7628 KB Ok
2 Correct 498 ms 7580 KB Ok
3 Correct 500 ms 7504 KB Ok
4 Correct 258 ms 3864 KB Ok
5 Correct 243 ms 3876 KB Ok
6 Correct 111 ms 2144 KB Ok
7 Correct 113 ms 2148 KB Ok
8 Correct 54 ms 1388 KB Ok
9 Correct 55 ms 1320 KB Ok
10 Correct 25 ms 748 KB Ok
11 Correct 2 ms 364 KB Ok
12 Correct 2 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 508 ms 7756 KB Ok
2 Correct 236 ms 3800 KB Ok
3 Correct 2 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 12 ms 492 KB Ok
8 Correct 238 ms 3876 KB Ok
9 Correct 125 ms 2116 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 3 ms 364 KB Ok
12 Correct 53 ms 1388 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 500 ms 7628 KB Ok
15 Correct 498 ms 7580 KB Ok
16 Correct 500 ms 7504 KB Ok
17 Correct 258 ms 3864 KB Ok
18 Correct 243 ms 3876 KB Ok
19 Correct 111 ms 2144 KB Ok
20 Correct 113 ms 2148 KB Ok
21 Correct 54 ms 1388 KB Ok
22 Correct 55 ms 1320 KB Ok
23 Correct 25 ms 748 KB Ok
24 Correct 2 ms 364 KB Ok
25 Correct 2 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 497 ms 7632 KB Ok
28 Correct 235 ms 3872 KB Ok
29 Correct 498 ms 7504 KB Ok
30 Correct 26 ms 748 KB Ok
31 Correct 2 ms 364 KB Ok
32 Correct 12 ms 492 KB Ok
33 Correct 54 ms 1196 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 0 ms 364 KB Ok
38 Correct 239 ms 3872 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 3872 KB Ok
2 Correct 497 ms 7504 KB Ok
3 Correct 496 ms 7632 KB Ok
4 Correct 26 ms 876 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 52 ms 1196 KB Ok
7 Correct 497 ms 7472 KB Ok
8 Correct 2 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 2 ms 364 KB Ok
11 Correct 111 ms 2148 KB Ok
12 Correct 235 ms 3872 KB Ok