CSES - Datatähti 2018 alku - Results
Submission details
Task:Fraktaali
Sender:eliaskosunen
Submission time:2017-10-03 00:31:48 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED10
#3ACCEPTED10
#4ACCEPTED10
#5ACCEPTED10
#6ACCEPTED10
#7ACCEPTED10
#8ACCEPTED10
#9ACCEPTED10
#10ACCEPTED10
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.04 s2details
#3ACCEPTED0.05 s3details
#4ACCEPTED0.03 s4details
#5ACCEPTED0.04 s5details
#6ACCEPTED0.04 s6details
#7ACCEPTED0.03 s7details
#8ACCEPTED0.05 s8details
#9ACCEPTED0.05 s9details
#10ACCEPTED0.11 s10details

Code

#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <memory>
#include <string>
#include <vector>

template <typename T, typename... Args>
std::unique_ptr<T> make_unique(Args&&... args)
{
    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}

constexpr int pow2(int n)
{
    return 1 << n;
}

struct boolean {
    constexpr boolean() = default;
    constexpr boolean(bool v) : val(v) {}

    constexpr explicit operator bool() const
    {
        return val;
    }

    void flip()
    {
        val = !val;
    }

private:
    bool val{false};
};

template <typename T>
class basic_square {
public:
    using value_type = T;

    basic_square() = default;
    basic_square(value_type value) : m_value{value} {}
    basic_square(int n);

    value_type& at(std::ptrdiff_t row, std::ptrdiff_t col);

    int size() const
    {
        if (has_subs()) {
            return m_subsquares[0].size() * 2;
        }
        return 1;
    }

    basic_square<value_type>& get(int i)
    {
        return m_subsquares[i];
    }

    void set(int i, basic_square<value_type> sq)
    {
        assert(has_subs());
        m_subsquares[i] = std::move(sq);
    }
    void set(value_type v)
    {
        assert(!has_subs());
        m_value = v;
    }
    void set(int i, value_type v)
    {
        m_subsquares[i] = v;
    }

    basic_square<value_type>& flip()
    {
        if (has_subs()) {
            for (auto& sub : m_subsquares) {
                sub.flip();
            }
            return *this;
        }
        m_value = !m_value;
        return *this;
    }

    static basic_square<value_type> flip(basic_square<value_type> s)
    {
        s.flip();
        return s;
    }

    void set_parent(basic_square<value_type>* p)
    {
        m_parent = p;
    }
    basic_square<value_type>* get_parent() const
    {
        return m_parent;
    }

    void set_parents(basic_square<value_type>* p = nullptr)
    {
        set_parent(p);
        for (auto& sub : m_subsquares) {
            sub.set_parents(this);
        }
    }

    basic_square& get_topleft();

private:
    bool has_subs() const
    {
        return m_subsquares.size() == 4;
    }

    std::vector<basic_square<value_type>> m_subsquares{};
    basic_square<value_type>* m_parent{nullptr};
    bool m_value{};
};

template <typename T>
inline basic_square<T>::basic_square(int n)
{
    if (n == 1) {
        m_value = {};
        return;
    }
    m_subsquares.resize(4, {});
    for (auto& sub : m_subsquares) {
        sub = basic_square<value_type>(n / 2);
    }
}

template <typename T>
inline typename basic_square<T>::value_type& basic_square<T>::at(
    std::ptrdiff_t row,
    std::ptrdiff_t col)
{
    if (!has_subs()) {
        return m_value;
    }
    const auto subsize = m_subsquares[0].size();
    if (row < subsize) {
        if (col < subsize) {
            return m_subsquares[0].at(row, col);
        }
        return m_subsquares[1].at(row, col - subsize);
    }
    if (col < subsize) {
        return m_subsquares[2].at(row - subsize, col);
    }
    return m_subsquares[3].at(row - subsize, col - subsize);
}

template <typename T>
inline basic_square<T>& basic_square<T>::get_topleft()
{
    if (!has_subs()) {
        return *this;
    }
    return m_subsquares[0].get_topleft();
}

using square = basic_square<bool>;

class fractal {
public:
    fractal(int n)
    {
        if (n == 1) {
            m_sq = square{1};
        }
        else {
            m_sq = square{pow2(n - 1)};
        }

        m_sq.at(0, 0) = true;
        if (n == 1) {
            return;
        }

        m_sq.set_parents();
        auto topleft = &m_sq.get_topleft();
        for (auto i = 0; i < n; ++i) {
            if (!topleft->get_parent()) {
                /* m_sq.set(1, *topleft); */
                /* m_sq.set(2, *topleft); */
                /* m_sq.set(3, square::flip(*topleft)); */
                break;
            }
            else {
                topleft->get_parent()->set(1, *topleft);
                topleft->get_parent()->set(2, *topleft);
                topleft->get_parent()->set(3, square::flip(*topleft));
                topleft = topleft->get_parent();
            }
        }
    }

    friend std::ostream& operator<<(std::ostream& os, fractal& f)
    {
        const auto size = f.m_sq.size();
        for (auto row = 0; row < size; ++row) {
            for (auto col = 0; col < size; ++col) {
                os << (f.m_sq.at(row, col) ? '#' : '.');
            }
            os << '\n';
        }
        return os;
    }

private:
    square m_sq{};
};

int main()
{
    int n;
    std::cin >> n;
    fractal f(n);
    std::cout << f;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1

correct output
#

user output
#

Test 2

Group: 2

Verdict: ACCEPTED

input
2

correct output
##
#.

user output
##
#.

Test 3

Group: 3

Verdict: ACCEPTED

input
3

correct output
####
#.#.
##..
#..#

user output
####
#.#.
##..
#..#

Test 4

Group: 4

Verdict: ACCEPTED

input
4

correct output
########
#.#.#.#.
##..##..
#..##..#
####....
...

user output
########
#.#.#.#.
##..##..
#..##..#
####....
...

Test 5

Group: 5

Verdict: ACCEPTED

input
5

correct output
################
#.#.#.#.#.#.#.#.
##..##..##..##..
#..##..##..##..#
####....####....
...

user output
################
#.#.#.#.#.#.#.#.
##..##..##..##..
#..##..##..##..#
####....####....
...

Test 6

Group: 6

Verdict: ACCEPTED

input
6

correct output
##############################...

user output
##############################...

Test 7

Group: 7

Verdict: ACCEPTED

input
7

correct output
##############################...

user output
##############################...

Test 8

Group: 8

Verdict: ACCEPTED

input
8

correct output
##############################...

user output
##############################...

Test 9

Group: 9

Verdict: ACCEPTED

input
9

correct output
##############################...

user output
##############################...

Test 10

Group: 10

Verdict: ACCEPTED

input
10

correct output
##############################...

user output
##############################...