oj.uz

Submission #336528

# Submission time Handle Problem Language Result Execution time Memory
336528 2020-12-15T14:11:03 Z Kerim "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 509 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 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 364 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 364 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 7460 KB Ok
2 Correct 238 ms 3948 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 236 ms 3876 KB Ok
4 Correct 112 ms 2116 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 4 ms 364 KB Ok
7 Correct 54 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 509 ms 7756 KB Ok
2 Correct 506 ms 7472 KB Ok
3 Correct 501 ms 7504 KB Ok
4 Correct 234 ms 3992 KB Ok
5 Correct 239 ms 4004 KB Ok
6 Correct 110 ms 2144 KB Ok
7 Correct 116 ms 2148 KB Ok
8 Correct 52 ms 1260 KB Ok
9 Correct 53 ms 1192 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 502 ms 7460 KB Ok
2 Correct 238 ms 3948 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 236 ms 3876 KB Ok
9 Correct 112 ms 2116 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 4 ms 364 KB Ok
12 Correct 54 ms 1388 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 509 ms 7756 KB Ok
15 Correct 506 ms 7472 KB Ok
16 Correct 501 ms 7504 KB Ok
17 Correct 234 ms 3992 KB Ok
18 Correct 239 ms 4004 KB Ok
19 Correct 110 ms 2144 KB Ok
20 Correct 116 ms 2148 KB Ok
21 Correct 52 ms 1260 KB Ok
22 Correct 53 ms 1192 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 7504 KB Ok
28 Correct 235 ms 3872 KB Ok
29 Correct 506 ms 7632 KB Ok
30 Correct 25 ms 748 KB Ok
31 Correct 2 ms 364 KB Ok
32 Correct 12 ms 492 KB Ok
33 Correct 53 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 1 ms 364 KB Ok
38 Correct 238 ms 3872 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 3872 KB Ok
2 Correct 507 ms 7632 KB Ok
3 Correct 503 ms 7504 KB Ok
4 Correct 25 ms 876 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 55 ms 1196 KB Ok
7 Correct 504 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 239 ms 3872 KB Ok