Submission #1338539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338539		MisterReaper	Broken Device 2 (JOI22_device2)	C++20	63 / 100	763 ms	11584 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using i64 = long long;

namespace {

#ifdef DEBUG
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int M = 937;

std::vector<i64> f;
std::vector<i64> g;

bool precalc_done = false;
void precalc() {
    if (precalc_done) {
        return;
    }
    f.assign(M + 1, 1);
    g.assign(M + 1, 1);
    i64 sum = 0;
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j <= i / 2; ++j){
            f[i] = std::max(f[i], f[j] * (i - j * 2 + 1));
        }
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k + j <= i; ++k) {
                g[i] = std::max(g[i], f[j] * f[k] * (2 * (i - j - k) + 1));
            }
        }
        sum += g[i];
        // debug(i, g[i], sum);
    }
    precalc_done = true;
}

std::vector<int> encode(int n, i64 x) {
    if (n == 0) {
        assert(x == 0);
        return {};
    }
    std::vector<int> res;
    for (int i = n / 2; i >= 0; --i) {
        if (f[n] == f[i] * (n - 2 * i + 1)) {
            int c = n - 2 * i + 1;
            int d = x % c;
            for (int j = 0; j < c - 1; ++j) {
                res.emplace_back(j < d);
            }
            auto v = encode(i, x / c);
            debug(res, v);
            res.insert(res.begin(), v.begin(), v.end());
            res.insert(res.end(), v.begin(), v.end());
            return res;
        }
    }
    assert(false);
    return res;
}

};

int Declare() {
    precalc();
    return M;
}

std::pair<std::vector<int>, std::vector<int>> Anna(i64 A) {
    --A;
    for (int i = 1; i <= M; ++i) {
        if (A >= g[i]) {
            A -= g[i];
            continue;
        }
        debug(i, A);
        bool good = false;
        std::vector<int> a(i, -1), b(i, -1);
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k + j <= i; ++k) {
                if (f[j] * f[k] * (2 * (i - j - k) + 1) == g[i]) {
                    debug(j, k, f[j], f[k]);
                    i64 x = A % f[j];
                    i64 y = A / f[j] % f[k];
                    i64 z = A / f[j] / f[k] % (2 * (i - j - k) + 1);
                    debug(x, y, z);
                    std::vector<int> p0 = encode(j, x);
                    std::vector<int> p1 = encode(k, y);
                    debug(p0, p1);
                    for (int l = 0; l < j; ++l) {
                        a[l] = p0[l];
                        b[j - 1 - l] = p0[l];
                    }
                    for (int l = 0; l < k; ++l) {
                        a[i - 1 - l] = p1[l];
                        b[i - (k - l)] = p1[l];
                    }
                    int cnt = 0;
                    for (int l = 0; l < i - j - k; ++l) {
                        a[j + l] = cnt < z;
                        cnt += 1;
                    }
                    for (int l = 0; l < i - j - k; ++l) {
                        b[j + l] = cnt < z;
                        cnt += 1;
                    }
                    good = true;
                    break;
                }
            }
            if (good) {
                break;
            }
        }
        debug(a, b);
        return {a, b};
    }
    assert(false);
    return {{}, {}};
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using i64 = long long;

namespace {

#ifdef DEBUG
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int M = 937;

std::vector<i64> f;
std::vector<i64> g;

bool precalc_done = false;
void precalc() {
    if (precalc_done) {
        return;
    }
    f.assign(M + 1, 1);
    g.assign(M + 1, 1);
    i64 sum = 0;
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j <= i / 2; ++j){
            f[i] = std::max(f[i], f[j] * (i - j * 2 + 1));
        }
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k + j <= i; ++k) {
                g[i] = std::max(g[i], f[j] * f[k] * (2 * (i - j - k) + 1));
            }
        }
        sum += g[i];
        // debug(i, g[i], sum);
    }
    precalc_done = true;
}

int one_count(std::vector<int> v);

i64 decode(std::vector<int> v) {
    int n = int(v.size());
    if (n == 0) {
        return 0;
    }
    for (int i = n / 2; i >= 0; --i) {
        if (f[n] == f[i] * (n - 2 * i + 1)) {
            int c = n - 2 * i + 1;
            int d = n % c;
            std::vector<int> u(v.begin(), v.begin() + i);
            i64 x = decode(u);
            debug(v, u, x, c, one_count(v) - 2 * one_count(u));
            x = x * c + one_count(v) - 2 * one_count(u);
            return x;
        }
    }
    assert(false);
    return 0;
}

int one_count(std::vector<int> v) {
    int n = int(v.size());
    return std::count(v.begin(), v.end(), 1);
}

};

i64 Bruno(std::vector<int> u) {
    precalc();
    int n = int(u.size()) / 2;
    i64 A = 0;
    for (int i = 1; i < n; ++i) {
        A += g[i];
    }
    debug(n);
    debug(u);
    bool good = false;
    for (int j = 0; j <= n; ++j) {
        for (int k = 0; k + j <= n; ++k) {
            if (f[j] * f[k] * (2 * (n - j - k) + 1) == g[n]) {
                debug(j, k, f[j], f[k]);
                std::vector<int> p0(u.begin(), u.begin() + j);
                std::vector<int> p1(u.end() - k, u.end());
                std::reverse(p1.begin(), p1.end());
                i64 x = decode(p0);
                i64 y = decode(p1);
                i64 z = one_count(u) - 2 * one_count(p0) - 2 * one_count(p1);
                debug(p0, p1, one_count(p0), one_count(p1));
                debug(x, y, z);
                A += x + y * f[j] + z * f[j] * f[k];
                good = true;
                break;
            }
        }
        if (good) {
            break;
        }
    }
    return A + 1;
}

Compilation message (stderr)

# 2번째 컴파일 단계

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/c++allocator.h:33,
                 from /usr/include/c++/13/bits/allocator.h:46,
                 from /usr/include/c++/13/vector:63,
                 from Bruno.h:2,
                 from Bruno.cpp:1:
In member function 'void std::__new_allocator<_Tp>::deallocate(_Tp*, size_type) [with _Tp = int]',
    inlined from 'constexpr void std::allocator< <template-parameter-1-1> >::deallocate(_Tp*, std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:210:35,
    inlined from 'static constexpr void std::allocator_traits<std::allocator<_Up> >::deallocate(allocator_type&, pointer, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:517:23,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(pointer, std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:390:19,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:369:15,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::~vector() [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:738:7,
    inlined from 'i64 {anonymous}::decode(std::vector<int>)' at Bruno.cpp:56:53:
/usr/include/c++/13/bits/new_allocator.h:172:33: warning: 'void operator delete(void*, std::size_t)' called on pointer '<unknown>' with nonzero offset [1, 4294967292] [-Wfree-nonheap-object]
  172 |         _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));
      |                                 ^
In member function '_Tp* std::__new_allocator<_Tp>::allocate(size_type, const void*) [with _Tp = int]',
    inlined from 'constexpr _Tp* std::allocator< <template-parameter-1-1> >::allocate(std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:198:40,
    inlined from 'static constexpr _Tp* std::allocator_traits<std::allocator<_Up> >::allocate(allocator_type&, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:482:28,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:381:33,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:378:7,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_create_storage(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:398:44,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::_Vector_base(std::size_t, const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:335:26,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:603:61,
    inlined from 'i64 {anonymous}::decode(std::vector<int>)' at Bruno.cpp:56:53:
/usr/include/c++/13/bits/new_allocator.h:151:55: note: returned from 'void* operator new(std::size_t)'
  151 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
      |                                                       ^
In member function 'void std::__new_allocator<_Tp>::deallocate(_Tp*, size_type) [with _Tp = int]',
    inlined from 'constexpr void std::allocator< <template-parameter-1-1> >::deallocate(_Tp*, std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:210:35,
    inlined from 'static constexpr void std::allocator_traits<std::allocator<_Up> >::deallocate(allocator_type&, pointer, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:517:23,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(pointer, std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:390:19,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:369:15,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::~vector() [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:738:7,
    inlined from 'i64 {anonymous}::decode(std::vector<int>)' at Bruno.cpp:56:53:
/usr/include/c++/13/bits/new_allocator.h:172:33: warning: 'void operator delete(void*, std::size_t)' called on pointer '<unknown>' with nonzero offset [1, 4294967292] [-Wfree-nonheap-object]
  172 |         _GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));
      |                                 ^
In member function '_Tp* std::__new_allocator<_Tp>::allocate(size_type, const void*) [with _Tp = int]',
    inlined from 'constexpr _Tp* std::allocator< <template-parameter-1-1> >::allocate(std::size_t) [with _Tp = int]' at /usr/include/c++/13/bits/allocator.h:198:40,
    inlined from 'static constexpr _Tp* std::allocator_traits<std::allocator<_Up> >::allocate(allocator_type&, size_type) [with _Tp = int]' at /usr/include/c++/13/bits/alloc_traits.h:482:28,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:381:33,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:378:7,
    inlined from 'constexpr void std::_Vector_base<_Tp, _Alloc>::_M_create_storage(std::size_t) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:398:44,
    inlined from 'constexpr std::_Vector_base<_Tp, _Alloc>::_Vector_base(std::size_t, const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:335:26,
    inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]' at /usr/include/c++/13/bits/stl_vector.h:603:61,
    inlined from 'i64 {anonymous}::decode(std::vector<int>)' at Bruno.cpp:56:53:
/usr/include/c++/13/bits/new_allocator.h:151:55: note: returned from 'void* operator new(std::size_t)'
  151 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
      |                                                       ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 23 / 60