Bittilista

input/code.cpp: In function 'bool isEven(std::vector<bool>&)':
input/code.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < b.size(); i++) {
                    ^

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <bitset>


using namespace std;
typedef long long LL;


vector<int> create(int bits) {
	LL total = (LL)1<<(bits);
	vector<int> res(total);

	for (int i = 0; i < total; i++) {
		res[i] = i;
	}

	return res;
}


bool isEven(vector<bool> & b) {
	if (b.size() == 1) return true;
	int zeroone = 0;
	int onezero = 0;
	for (int i = 1; i < b.size(); i++) {
		if (b[i-1] == 0 && b[i] == 1) zeroone++;
		else if (b[i-1] == 1 && b[i] == 0) onezero++;
	}
	return zeroone == onezero;
}

/*int getDiff(vector<bool> & b) { // get diff of "01"s minus "10"s
	if (b.size() == 1) return 0;
	int zeroone = 0;
	int onezero = 0;
	for (int i = 1; i < b.size(); i++) {
		if (b[i-1] == 0 && b[i] == 1) zeroone++;
		else if (b[i-1] == 1 && b[i] == 0) onezero++;
	}
	return zeroone - onezero;
}*/

int getDiff(int b, int bitsize) { // get diff of "01"s minus "10"s
	int zeroone = 0;
	int onezero = 0;
//cout << b << " " << (b & 3) << " " << bitsize << " ";
	for (int i = 0; i < bitsize - 1; i++) {
		if ((b & 3) == 1) {
			zeroone++;
		} else if ((b & 3) == 2) {
			onezero++;
		}
		b >>= 1;
	}
//cout << zeroone << " " << onezero << endl;
	return zeroone - onezero;	
}


void printres(int b1, int bits1, int b2, int bits2) {
	for (int i = bits1 - 1; i >= 0; i--) {
		cout << (int) ((b1 >> i) & 1);
	}
	for (int i = bits2 - 1; i >= 0; i--) {
		cout << (int) ((b2 >> i) & 1);
	}
}

void printvec(int b1, int bits1) {
	for (int i = bits1 - 1; i >= 0; i--) {
		cout << (int) ((b1 >> i) & 1);
	}
	cout << endl;
}


void brute(int n, int k) {
	auto v = create(n);
	vector<int> asd;
//for (auto a : v) cout << a << " "; cout << endl;
	for (auto v1 : v) {
//cout << v1 << " " << getDiff(v1, n) << endl;
		if (getDiff(v1, n) == 0) {
			asd.push_back(v1);
		}
	}
//for (auto a : asd) cout << a << " "; cout << endl;
	sort(asd.begin(), asd.end());
	printvec(asd[k-1], n);
}


int main() {
	int n, k;
	cin >> n >> k;

	if (n <= 5) {
		brute(n,k);
		return 0;
	}
	//
	//

	int bits1 = n/2;
	int bits2 = n/2 + n%2;

//cout << "QWEWQE" << endl;
	vector<int> r1 = create(bits1);
//cout << "QWEWQE" << endl;
	vector<int> r2 = create(bits2);
cout << "QWEWQE" << endl;
//for (auto v : r2) printvec(v);
//cout << endl;
	unordered_map<int, vector<int>> startWithOne;
	unordered_map<int, vector<int>> startWithZero;

	for (int v : r2) {
		int diff = getDiff(v, bits2);
		if (v >> (bits2-1) == 0) {
			startWithZero[diff].push_back(v);
		} else {
			startWithOne[diff].push_back(v);
		}
	}
cout << "QWEWQE" << endl;
	sort(r1.begin(), r1.end());

	for (int v : r1) {
		int diff = getDiff(v, bits1);

		int s = 0;
		if ((v & 1) == 0) {
			s += startWithZero[-diff].size();
			s += startWithOne[-diff - 1].size();
		} else {
			s += startWithZero[-diff + 1].size();
			s += startWithOne[-diff].size();
		}

		if (k <= s) {
			vector<int> temp;
			if ((v & 1) == 0) {
				move(startWithZero[-diff].begin(), startWithZero[-diff].end(), back_inserter(temp));
				move(startWithOne[-diff - 1].begin(), startWithOne[-diff - 1].end(), back_inserter(temp));
			} else {
				move(startWithZero[-diff + 1].begin(), startWithZero[-diff + 1].end(), back_inserter(temp));
				move(startWithOne[-diff].begin(), startWithOne[-diff].end(), back_inserter(temp));
			}
			sort(temp.begin(), temp.end());
			
			printres(v, bits1, temp[k-1], bits2);
			return 0;
		} else {
			k -= s;
		}
	}

	/*
	for (auto & v : r1) {
		if (isEven(v)) {
			res1.push_back(v);
		}
	}

	for (auto & v : r2) {
		if (isEven(v)) {
			res2.push_back(v);
		}
	}


	sort(res2.begin(), res2.end());

	n--; // TODO ONE INDEXED correct?
	int first = n/res2.size();
	int second = n % res2.size();
	
	for (auto v : res1)	{ for (bool b : v) { cout << (int) b; } cout << endl; }

cout << res1.size() << " sizes " << res2.size() << endl;
	for (bool b : res1[first]) {
		cout << (int) b;
	}
cout << endl;
	for (bool b : res2[second]) {
		cout << (int) b;
	}
	*/

}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: RUNTIME ERROR

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: RUNTIME ERROR

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR