oj.uz

Submission #218835

# Submission time Handle Problem Language Result Execution time Memory
218835 2020-04-02T19:43:18 Z Lawliet "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 208 ms 6512 KB 
#include <bits/stdc++.h>

using namespace std;

int n, k, t;

vector< int > ans;

void printBinary(int k)
{
	for(int i = n - 1 ; i >= 0 ; i--)
	{
		if( k & (1 << i) ) printf("1");
		else printf("0");
	}

	printf("\n");
}

int toNumber(string s)
{
	int val = 0;

	for(int i = 0 ; i < s.size() ; i++)
	{
		val *= 2;
		val += s[i] - '0';
	}

	return val;
}

bool isGood(int a, int b, int v)
{
	int aux = a^b;
	return ( __builtin_popcount(aux) == v );
}

void printAnswer(int firstValue)
{
	printf("%d\n",(int) ans.size());

	int indFirst = 0;

	for(int i = 0 ; i < ans.size() ; i++)
		if( ans[i] == firstValue ) indFirst = i;

	int lim = indFirst - 1;
	if( lim == -1 ) lim = ans.size() - 1;

	for(int i = indFirst ; i != lim ; i++, i %= ans.size())
		printBinary( ans[i] );

	printBinary( ans[lim] );
}

int main()
{
	string s;
	cin >> n >> k >> t >> s;

	if( k%2 == 0 )
	{
		printf("-1\n");
		return 0;
	}

	int firstValue = toNumber( s );

	ans.push_back( 0 );
	ans.push_back( 1 );

	for(int i = 2 ; i <= k + 1 ; i++)
	{
		int curSz = ans.size();

		for(int j = 0 ; j < ans.size() ; j++)
			ans[j] = 2*ans[j];

		for(int j = curSz - 1 ; j >= 0 ; j--)
			ans.push_back( ans[j] + 1 );
	}

	if( k == 1 )
	{
		for(int i = k + 2 ; i <= n ; i++)
		{
			int curSz = ans.size();

			for(int j = 0 ; j < ans.size() ; j++)
				ans[j] = 2*ans[j];

			for(int j = curSz - 1 ; j >= 0 ; j--)
				ans.push_back( ans[j] + 1 );
		}

		printAnswer( firstValue );
		return 0;
	}

	for(int i = 1 ; i < ans.size() ; i += 2)
		ans[i] = (1 << (k + 1)) - 1 - ans[i];

	for(int i = k + 2 ; i <= n ; i++)
	{
		int curSz = ans.size();

		int indFirst = -1;

		for(int j = 1 ; j < ans.size() && indFirst == -1 ; j++)
		{
			if( !isGood( ans[j] , ans.back() , k - 1 ) ) continue;
			if( !isGood( ans[j - 1] , ans[0] , k - 1 ) ) continue;

			indFirst = j;
		}

		assert( indFirst != -1 );

		for(int j = 0 ; j < ans.size() ; j++)
			ans[j] = 2*ans[j];

		int lim = indFirst - 1;
		if( lim == -1 ) lim = curSz - 1;

		for(int j = indFirst ; j != lim ; j++, j %= curSz)
			ans.push_back( ans[j] + 1 );

		ans.push_back( ans[lim] + 1 );
	}

	printAnswer( firstValue );
}

Compilation message

lyuboyn.cpp: In function 'int toNumber(std::__cxx11::string)':
lyuboyn.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < s.size() ; i++)
                  ~~^~~~~~~~~~
lyuboyn.cpp: In function 'void printAnswer(int)':
lyuboyn.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < ans.size() ; i++)
                  ~~^~~~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < ans.size() ; j++)
                   ~~^~~~~~~~~~~~
lyuboyn.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < ans.size() ; j++)
                    ~~^~~~~~~~~~~~
lyuboyn.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < ans.size() ; i += 2)
                  ~~^~~~~~~~~~~~
lyuboyn.cpp:110:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1 ; j < ans.size() && indFirst == -1 ; j++)
                   ~~^~~~~~~~~~~~
lyuboyn.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < ans.size() ; j++)
                   ~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 6504 KB Ok
2 Correct 96 ms 3312 KB Ok
3 Correct 5 ms 384 KB Ok
4 Correct 4 ms 256 KB Ok
5 Correct 4 ms 384 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Ok
2 Correct 9 ms 512 KB Ok
3 Correct 100 ms 3312 KB Ok
4 Correct 47 ms 1780 KB Ok
5 Correct 5 ms 384 KB Ok
6 Correct 5 ms 384 KB Ok
7 Correct 26 ms 1152 KB Ok
8 Correct 5 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 6480 KB Ok
2 Correct 191 ms 6508 KB Ok
3 Correct 192 ms 6508 KB Ok
4 Correct 96 ms 3312 KB Ok
5 Correct 95 ms 3312 KB Ok
6 Correct 49 ms 1780 KB Ok
7 Correct 47 ms 1780 KB Ok
8 Correct 26 ms 1144 KB Ok
9 Correct 26 ms 1152 KB Ok
10 Correct 14 ms 640 KB Ok
11 Correct 5 ms 384 KB Ok
12 Correct 5 ms 384 KB Ok
13 Correct 5 ms 256 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 6504 KB Ok
2 Correct 96 ms 3312 KB Ok
3 Correct 5 ms 384 KB Ok
4 Correct 4 ms 256 KB Ok
5 Correct 4 ms 384 KB Ok
6 Correct 5 ms 256 KB Ok
7 Correct 9 ms 512 KB Ok
8 Correct 100 ms 3312 KB Ok
9 Correct 47 ms 1780 KB Ok
10 Correct 5 ms 384 KB Ok
11 Correct 5 ms 384 KB Ok
12 Correct 26 ms 1152 KB Ok
13 Correct 5 ms 384 KB Ok
14 Correct 199 ms 6480 KB Ok
15 Correct 191 ms 6508 KB Ok
16 Correct 192 ms 6508 KB Ok
17 Correct 96 ms 3312 KB Ok
18 Correct 95 ms 3312 KB Ok
19 Correct 49 ms 1780 KB Ok
20 Correct 47 ms 1780 KB Ok
21 Correct 26 ms 1144 KB Ok
22 Correct 26 ms 1152 KB Ok
23 Correct 14 ms 640 KB Ok
24 Correct 5 ms 384 KB Ok
25 Correct 5 ms 384 KB Ok
26 Correct 5 ms 256 KB Ok
27 Correct 198 ms 6508 KB Ok
28 Correct 103 ms 3312 KB Ok
29 Correct 208 ms 6512 KB Ok
30 Correct 14 ms 640 KB Ok
31 Correct 5 ms 384 KB Ok
32 Correct 11 ms 512 KB Ok
33 Correct 25 ms 1152 KB Ok
34 Correct 5 ms 384 KB Ok
35 Correct 4 ms 256 KB Ok
36 Correct 5 ms 384 KB Ok
37 Correct 5 ms 256 KB Ok
38 Correct 104 ms 3308 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 3312 KB Ok
2 Correct 205 ms 6504 KB Ok
3 Correct 200 ms 6504 KB Ok
4 Correct 15 ms 640 KB Ok
5 Correct 5 ms 384 KB Ok
6 Correct 26 ms 1144 KB Ok
7 Correct 194 ms 6504 KB Ok
8 Correct 5 ms 384 KB Ok
9 Correct 4 ms 256 KB Ok
10 Correct 5 ms 384 KB Ok
11 Correct 49 ms 1780 KB Ok
12 Correct 95 ms 3312 KB Ok