oj.uz

Submission #336379

# Submission time Handle Problem Language Result Execution time Memory
336379 2020-12-15T06:01:16 Z tengiz05 "The Lyuboyn" code (IZhO19_lyuboyn) C++17
5 / 100
 1000 ms 3180 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int T, n, m, k;
string start;
vector<string> v;
vector<string> ans = {"-1"};
int pw;
int toint(string s){
	reverse(all(s));
	int res = 0;
	int p=1;
	for(auto x : s){
		res += (x-'0')*p;
		p*=2;
	}return res;
}
map<int, bool> used;
int count(string &s1, string &s2){
	int ans = 0;
	assert(s1.size() == s2.size());
	for(int i=0;i<s1.size();i++){
		if(s1[i] != s2[i])ans++;
	}return ans;
}

string tobin(int a){
	string res;
	for(int i=0;i<n;i++){
		res += a%2+'0';
		a>>=1;
	}reverse(all(res));
	return res;
}

void rec(int i=1){
	if(i == (1<<n)){
	//	for(auto x : v)cout << x << ' ';cout << '\n';
		for(int j=1;j<v.size();j++){
			if(count(v[j-1], v[j]) != k)return;
		}
		if(T == 1)if(count(v[0], v.back()) != k)return;
		ans = v;
		return;
	}
	for(int d=0;d<(1<<n);d++){
		if(used[d])continue;
		string tmp = tobin(d);
		if(count(v[i-1], tmp) != k)continue;
		v.pb(tobin(d));
		used[d] = true;
		rec(i+1);
		v.pop_back();
		used.erase(d);
	}
}
void solve(int test_case){
	int i, j;
	cin >> n >> k >> T;
	cin >> start;
	pw = 1;
	for(i=0;i<n;i++)pw*=2;
	used[toint(start)] = true;
	v.pb(start);
	rec(1);
	if(ans[0] == "-1"){
		cout << -1 << '\n';
		return;
	}
	cout << pw << '\n';
	for(auto x : ans)cout << x << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

lyuboyn.cpp: In function 'long long int count(std::string&, std::string&)':
lyuboyn.cpp:32:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0;i<s1.size();i++){
      |              ~^~~~~~~~~~
lyuboyn.cpp: In function 'void rec(long long int)':
lyuboyn.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j=1;j<v.size();j++){
      |               ~^~~~~~~~~
lyuboyn.cpp: In function 'void solve(long long int)':
lyuboyn.cpp:68:9: warning: unused variable 'j' [-Wunused-variable]
   68 |  int i, j;
      |         ^

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 42 ms 364 KB Ok

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 1472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 2936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 2832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 2936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 3180 KB Time limit exceeded
2 Halted 0 ms 0 KB -