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