Language: C++


#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

class Numoeba {
public:
    Numoeba(const int n) :max_cell_(1), root_(0) {create_cell(n);}
    tuple<int, int> die() {
        for(int step = 1; step <= 500; ++step) {
            max_cell_ = max(max_cell_, (int) dead_.size() - count(dead_.begin(), dead_.end(), true));
            vector<int> candidate;
            int new_leader_id, new_leader_n = NIL;
// cout<<step<<endl;
// cout<<"root: "<<root_<<endl;
// cout<<"dead: ";for(const auto&d:dead_)cout<<" "<<d;cout<<endl;
// cout<<"numb: ";for(const auto&d:numbosome_)cout<<" "<<d;cout<<endl;
            if(traverse(root_, NIL, candidate, new_leader_id, new_leader_n)) return tuple<int, int>(step, max_cell_);
            for(auto& e: edge_) for(int i = 0; i < e.size(); ++i) if(dead_[e[i]]) e.erase(e.begin() + i--);
// cout<<"candidate: ";for(const auto&d:candidate)cout<<" "<<d;cout<<endl;
            for(const auto& c: candidate) {
                int n = (numbosome_[c] + 1) / 2;
                if(!(n & 1)) ++n;
//                 if(n <= 1) continue;
//                 if(dead_[c]) continue;
                add_child(c, create_cell(n));
            }
            if(new_leader_id == NIL) continue;
            root_ = new_leader_id;
            int n = (numbosome_[root_] + 1) / 2;
            if(!(n & 1)) --n;
//             if(n <= 1) continue;
            add_child(root_, create_cell(n));
        }
        return tuple<int, int>(NIL, max_cell_);
    }
private:
    const int MOD = 12345678;
    const int NIL = -1;
    bool traverse(const int current, const int previous, vector<int>& candidate, int& new_leader_id, int& new_leader_n) {
        int pn = numbosome_[current];
        if(update(current) == 1) {
            dead_[current] = true;
            if(current == root_) return true;
            if(edge_[current].size() == 2) {
                int next = edge_[current][0];
                if(next == previous) next = edge_[current][1];
                for(auto& id: edge_[previous]) if(id == current) id = next;
                for(auto& id: edge_[next]) if(id == current) id = previous;
                return traverse(next, previous, candidate, new_leader_id, new_leader_n);
            }
            for(const auto& next: edge_[current]) if(next != previous) erase(next, current);
            return false;
        }
        if(numbosome_[current] > pn && edge_[current].size() <= 1) candidate.push_back(current);
        if(numbosome_[current] == new_leader_n) new_leader_id = NIL;
        if(numbosome_[current] > new_leader_n) {
            new_leader_n = numbosome_[current];
            new_leader_id = current;
        }
        for(const auto& next: edge_[current]) {
            if(next == previous) continue;
            if(traverse(next, current, candidate, new_leader_id, new_leader_n)) return true;
        }
        return false;
    }
    void erase(const int current, const int previous) {
        dead_[current] = true;
        for(const auto& next: edge_[current]) if(next != previous) erase(next, current);
    }
    int create_cell(const int n) {
        numbosome_.push_back(n);
        dead_.push_back(false);
        edge_.push_back(vector<int>());
        return (dead_.size() - 1);
    }
    void add_child(const int pid, const int cid) {
        edge_[pid].push_back(cid);
        edge_[cid].push_back(pid);
    }
    int update(const int id) {
        numbosome_[id] = numbosome_[id] * 3 + 1;
        while(!(numbosome_[id] & 1)) numbosome_[id] >>= 1;
        if(numbosome_[id] > MOD) numbosome_[id] -= MOD;
//         while(numbosome_[id] > MOD) numbosome_[id] -= MOD;
        return numbosome_[id];
    }
    int root_;
    int max_cell_;
    vector<int> numbosome_;
    vector<bool> dead_;
    vector<vector<int>> edge_;
public:
void print(){
cout<<"root: "<<root_<<endl;
cout<<"dead: ";for(const auto&d:dead_)cout<<" "<<d;cout<<endl;
cout<<"numb: ";for(const auto&d:numbosome_)cout<<" "<<d;cout<<endl;
cout<<dead_.size()<<endl;
}
};


int main() {
    int k;
    while(cin >> k, k) {
        Numoeba n(k);
        int step, numbosome;
        tie(step, numbosome) = n.die();
        cout << step << " " << numbosome << endl;
//         n.print();
    }
}

Compiler output:
a.cc: In member function 'std::tuple<int, int> Numoeba::die()':
a.cc:13:28: error: no matching function for call to 'max(int&, std::__iterator_traits<std::_Bit_iterator, void>::difference_type)'
   13 |             max_cell_ = max(max_cell_, (int) dead_.size() - count(dead_.begin(), dead_.end(), true));
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:13:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<std::_Bit_iterator, void>::difference_type' {aka 'long int'})
   13 |             max_cell_ = max(max_cell_, (int) dead_.size() - count(dead_.begin(), dead_.end(), true));
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:5:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:13:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   13 |             max_cell_ = max(max_cell_, (int) dead_.size() - count(dead_.begin(), dead_.end(), true));
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~