結果

問題 No.884 Eat and Add
ユーザー PachicobuePachicobue
提出日時 2019-09-13 21:48:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 8,098 bytes
コンパイル時間 2,659 ms
コンパイル使用メモリ 202,764 KB
最終ジャッジ日時 2025-01-07 17:48:13
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wsign-conversion"
#define NDEBUG
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using uint = unsigned int;
using usize = std::size_t;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T> constexpr T popcount(const T u) { return u ? static_cast<T>(__builtin_popcountll(static_cast<u64>(u))) : static_cast<T>(0); }
template<typename T> constexpr T log2p1(const T u) { return u ? static_cast<T>(64 - __builtin_clzll(static_cast<u64>(u))) : static_cast<T>(0); }
template<typename T> constexpr T msbp1(const T u) { return log2p1(u); }
template<typename T> constexpr T lsbp1(const T u) { return __builtin_ffsll(u); }
template<typename T> constexpr T clog(const T u) { return u ? log2p1(u - 1) : static_cast<T>(u); }
template<typename T> constexpr bool ispow2(const T u) { return u and (static_cast<u64>(u) & static_cast<u64>(u - 1)) == 0; }
template<typename T> constexpr T ceil2(const T u) { return static_cast<T>(1) << clog(u); }
template<typename T> constexpr T floor2(const T u) { return u == 0 ? static_cast<T>(0) : static_cast<T>(1) << (log2p1(u) - 1); }
template<typename T> constexpr bool btest(const T mask, const usize ind) { return ((static_cast<u64>(mask) >> ind) & static_cast<u64>(1)); }
template<typename T> constexpr T bcut(const T mask, const usize ind) { return ind == 0 ? static_cast<T>(0) : static_cast<T>((static_cast<u64>(mask)
    << (64 - ind)) >> (64 - ind)); }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
constexpr unsigned int mod = 1000000007;
template<typename T> constexpr T inf_v = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
/**
* http://xoshiro.di.unimi.it/xoshiro128starstar.c
* http://xoshiro.di.unimi.it/xoshiro256starstar.c
* http://xoshiro.di.unimi.it/splitmix64.c
*/
class xoshiro
{
public:
using result_type = uint32_t;
static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
xoshiro() : xoshiro(std::random_device{}()) {}
xoshiro(uint64_t seed)
{
uint64_t z = 0;
for (int i = 0; i < 4; i++) { z = (seed += 0x9e3779b97f4a7c15), z = (z ^ (z >> 33)) * 0x62A9D9ED799705F5, z = (z ^ (z >> 28)) *
            0xCB24D0A5C88C35B3, s[i] = static_cast<result_type>(z >> 32); }
}
result_type operator()()
{
const result_type result = rotl(s[1] * 5, 7) * 9, t = s[1] << 9;
return s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t, s[3] = rotl(s[3], 11), result;
}
void discard(const usize rep)
{
for (usize i = 0; i < rep; i++) { (*this)(); }
}
private:
result_type s[4];
static result_type rotl(const result_type x, const int k) { return (x << k) | (x >> (32 - k)); }
};
class xoshiro_64
{
public:
using result_type = uint64_t;
static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
xoshiro_64() : xoshiro_64(std::random_device{}()) {}
xoshiro_64(uint64_t seed)
{
uint64_t z = 0;
for (int i = 0; i < 4; i++) { z = (seed += 0x9e3779b97f4a7c15), z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9, z = (z ^ (z >> 27)) *
            0x94d049bb133111eb, s[i] = static_cast<result_type>(z ^ (z >> 31)); }
}
result_type operator()()
{
const result_type result = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
return s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t, s[3] = rotl(s[3], 45), result;
}
void discard(const usize rep)
{
for (usize i = 0; i < rep; i++) { (*this)(); }
}
private:
result_type s[4];
static result_type rotl(const result_type x, const int k) { return (x << k) | (x >> (64 - k)); }
};
template<typename Rng>
class rng_base
{
public:
using rng_type = Rng;
using result_type = typename rng_type::result_type;
static constexpr result_type min() { return rng_type::min(); }
static constexpr result_type max() { return rng_type::max(); }
rng_base() : rng_base(std::random_device{}()) {}
rng_base(const u64 seed) : rng(seed) {}
~rng_base() = default;
result_type operator()() { return rng(); }
template<typename Int>
Int uniform_int(const Int max)
{
static_assert(std::is_integral<Int>::value, "Integer type is needed.");
if (ispow2(max + 1)) { return static_cast<Int>(rng() & max); }
const result_type mask = static_cast<result_type>(ceil2(static_cast<u64>(max + 1))) - 1;
while (true) {
const Int ans = static_cast<Int>(rng() & mask);
if (ans <= max) { return ans; }
}
}
template<typename Int> Int uniform_int(const Int min, const Int max) { return min + uniform_int(static_cast<Int>(max - min)); }
bool uniform_bool() { return uniform_int<bool>(0, 1); }
template<typename Real>
Real uniform_real()
{
static_assert(std::is_floating_point<Real>::value, "FloatingPoint type is needed.");
return static_cast<Real>(uniformInt(~static_cast<result_type>(0)) / static_cast<Real>(~static_cast<result_type>(0)));
}
template<typename Real> Real uniform_real(const Real min, const Real max) { return assert(min <= max), uniform_real<Real>() * (max - min) + min;
        }
template<typename Int> std::pair<Int, Int> uniform_int_pair(const Int min, const Int max) { return std::minmax(uniform_int(min, max), uniform_int
        (min, max)); }
template<typename Int>
std::vector<Int> uniform_int_vec(const std::size_t size, const Int min, const Int max)
{
std::vector<Int> v(size);
for (std::size_t i = 0; i < size; i++) { v[i] = uniformInt(min, max); }
return v;
}
template<typename Real>
std::vector<Real> uniform_real_vec(const std::size_t size, const Real min, const Real max)
{
std::vector<Real> v(size);
for (std::size_t i = 0; i < size; i++) { v[i] = uniformReal(min, max); }
return v;
}
void discard(const usize rep) { rng.discard(rep); }
private:
Rng rng;
};
using rng_mt = rng_base<std::mt19937>;
using rng_mt64 = rng_base<std::mt19937_64>;
using rng_xoshiro = rng_base<xoshiro>;
using rng_xoshiro64 = rng_base<xoshiro_64>;
rng_mt g_rng_mt;
rng_mt64 g_rng_mt64;
rng_xoshiro g_rng_xo;
rng_xoshiro64 g_rng_xo64;
template<typename T>
T read()
{
T v;
return std::cin >> v, v;
}
template<typename T>
std::vector<T> read_vec(const std::size_t size)
{
std::vector<T> v(size);
for (auto& e : v) { std::cin >> e; }
return v;
}
#define SHOW(...) static_cast<void>(0)
template<typename T>
std::vector<T> make_v(const std::size_t size, T v) { return std::vector<T>(size, v); }
template<class... Args>
auto make_v(const std::size_t size, Args... args) { return std::vector<decltype(make_v(args...))>(size, make_v(args...)); }
int main()
{
std::cin.tie(nullptr), std::ios::sync_with_stdio(false);
const auto s = read<std::string>();
const usize n = s.size();
std::vector<std::string> t{""};
for (usize i = 0, z = 0; i < n; i++) {
if (s[i] == '0') {
z++;
} else {
if (z == 1) { t.back().push_back('0'); }
if (z >= 2) { t.push_back(""); }
z = 0;
t.back().push_back(s[i]);
}
}
int ans = 0;
for (const auto& s : t) {
if (s.empty()) { continue; }
int o = 0, z = 2;
for (const char c : s) {
if (c == '1') {
o++;
} else {
z++;
}
}
ans += std::min(o, z);
}
std::cout << ans << std::endl;
SHOW(t);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0