#include <cstddef>
#include <new>
#include <utility>
#include <stdexcept>

template<class T, size_t N>
class Allocator {
private:
    // Сырой буфер памяти под N объектов типа T
    alignas(T) unsigned char buffer_[sizeof(T) * N];

    // Связанный список индексов свободных слотов
    int freelist_[N];
    int free_head_; // индекс первой свободной ячейки

public:
    Allocator() {
        // Изначально все ячейки свободны
        for (int i = 0; i < N - 1; ++i)
            freelist_[i] = i + 1;
        freelist_[N - 1] = -1;
        free_head_ = 0;
    }

    template<typename... Args>
    T* AllocateAndConstruct(Args&&... args) {
        if (free_head_ == -1) {
            throw std::bad_alloc();
        }
        int index = free_head_;
        free_head_ = freelist_[index];

        T* ptr = reinterpret_cast<T*>(&buffer_[sizeof(T) * index]);
        new (ptr) T(std::forward<Args>(args)...); // placement new
        return ptr;
    }

    void DestroyAndDeallocate(T* ptr) {
        if (!ptr) return;

        ptr->~T(); // явный вызов деструктора

        // Вернуть ячейку в freelist
        auto index = (reinterpret_cast<unsigned char*>(ptr) - buffer_) / sizeof(T);
        freelist_[index] = free_head_;
        free_head_ = index;
    }
};