Submission #535278


Source Code Expand

// * template

#include <bits/stdc++.h>
#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; }
template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}

// * solve

inline long long popcount(long long x) {
	return __builtin_popcountll(x);
}

inline bool match(long long x, long long n) {
	return popcount(x) == popcount(x + n);
}

long long solve(const long long n) {
	const bitset<64> N(n);
	map<pair<int, int>, long long> dp;
	dp[make_pair(0, 0)] = 0ll;

	for(int i = 62; i >= 0; --i) {
		map<pair<int, int>, long long> next_dp;
		const auto update = [&next_dp](int d, int l, long long v) {
			const auto key = make_pair(d, l);
			if(next_dp.count(key)) {
				chmin(next_dp[key], v);
			}
			else {
				next_dp[key] = v;
			}
		};

		for(const auto &e : dp) {
			const int diff = e.first.first;
			const int len = e.first.second;
			const long long value = e.second;

			if(N[i]) { // 1
				update(diff - 1, len + 1, value); // 0
				update(diff + len, 0, value | (1ll << i)); // 1
			}
			else { // 0
				update(diff, 0, value); // 0
				update(diff, len + 1, value | (1ll << i)); // 1
			}
		}

		dp = move(next_dp);
	}

	long long x = LLONG_MAX;
	for(const auto &e : dp) {
		if(e.first.first == 0) chmin(x, e.second);
	}

	assert(match(x, n));
	return x;
}

int main(int argc, const char *const argv[]) {
#ifdef LOCAL
	init_debug(argc, argv);
#endif

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while(t--) {
		long long n;
		cin >> n;
		cout << solve(n) << endl;
	}

	return EXIT_SUCCESS;
}

Submission Info

Submission Time
Task H - Bit Count
User nisshy
Language C++11 (GCC 4.9.2)
Score 300
Code Size 2161 Byte
Status AC
Exec Time 1608 ms
Memory 1120 KB

Judge Result

Set Name All
Score / Max Score 300 / 300
Status
AC × 9
Set Name Test Cases
All 00_sample.txt, 10_small_00.txt, 20_medium_01.txt, 20_medium_02.txt, 20_medium_03.txt, 30_large_04.txt, 30_large_05.txt, 30_large_06.txt, 80_power_of_2.txt
Case Name Status Exec Time Memory
00_sample.txt AC 34 ms 980 KB
10_small_00.txt AC 120 ms 992 KB
20_medium_01.txt AC 508 ms 1008 KB
20_medium_02.txt AC 540 ms 980 KB
20_medium_03.txt AC 500 ms 980 KB
30_large_04.txt AC 1485 ms 1120 KB
30_large_05.txt AC 1608 ms 1120 KB
30_large_06.txt AC 1491 ms 1112 KB
80_power_of_2.txt AC 44 ms 988 KB