CSES - Putka Open 2015 – 6/6 - Results
Submission details
Task:Bittilista
Sender:
Submission time:2015-12-06 19:01:53 +0200
Language:C++
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED17
#2ACCEPTED28
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.07 s2details
#9ACCEPTED0.04 s2details
#10ACCEPTED0.05 s2details
#110.12 s3details
#120.12 s3details
#130.12 s3details
#140.12 s3details
#150.12 s3details

Compiler report

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++) {
                    ^

Code

#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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 54

correct output
0001101010

user output
0001101010

Test 2

Group: 1

Verdict: ACCEPTED

input
10 302

correct output
1001011011

user output
1001011011

Test 3

Group: 1

Verdict: ACCEPTED

input
10 241

correct output
0111100000

user output
0111100000

Test 4

Group: 1

Verdict: ACCEPTED

input
10 382

correct output
1011111011

user output
1011111011

Test 5

Group: 1

Verdict: ACCEPTED

input
10 138

correct output
0100010010

user output
0100010010

Test 6

Group: 2

Verdict: ACCEPTED

input
20 131002

correct output
00111111111101110010

user output
00111111111101110010

Test 7

Group: 2

Verdict: ACCEPTED

input
20 441567

correct output
11010111100110111101

user output
11010111100110111101

Test 8

Group: 2

Verdict: ACCEPTED

input
20 109770

correct output
00110101100110010010

user output
00110101100110010010

Test 9

Group: 2

Verdict: ACCEPTED

input
20 327308

correct output
10011111110100010111

user output
10011111110100010111

Test 10

Group: 2

Verdict: ACCEPTED

input
20 302918

correct output
10010011111010001011

user output
10010011111010001011

Test 11

Group: 3

Verdict:

input
50 216967103451763

correct output
011000101010101001001011100100...

user output
(empty)

Test 12

Group: 3

Verdict:

input
50 236618662270629

correct output
011010111001101000001001101001...

user output
(empty)

Test 13

Group: 3

Verdict:

input
50 426560943304480

correct output
110000011111101000111010110000...

user output
(empty)

Test 14

Group: 3

Verdict:

input
50 294553802415801

correct output
100001011111001010010011011000...

user output
(empty)

Test 15

Group: 3

Verdict:

input
50 502225394100883

correct output
111001000110001010111011000110...

user output
(empty)