⌨️

競技プログラミング用俺俺ライブラリまとめ

2021/05/20に公開
#include <assert.h>
#include <chrono>

/* マクロ */
#define DEBUG 0
#if DEBUG
#define ASSERT(x) assert(x)
#define LOG(x) cerr << x
#define LOG_UNLESS(x,exp) if(!(x)){LOG(exp);}
#else
#define ASSERT(x)
#define LOG(x)
#define LOG_UNLESS(x,exp)
#endif

/* 乱数生成 */
std::uint32_t XORShiftRandom() {
    static uint32_t y = 2463534241;
    y = y ^ (y << 13); y = y ^ (y >> 17);
    return y = y ^ (y << 5);
}
int XORShiftRandom(int n) {
    return XORShiftRandom()%n;
}
double XORShiftRandomDouble()
{
    return XORShiftRandom(UINT32_MAX) / (double)UINT32_MAX;
}
/* 時間計測 */
class StopWatch{
public:
    StopWatch(){}
    inline std::chrono::system_clock::time_point now() const {return std::chrono::system_clock::now();}
    void start(){mBegin = now();}
    double elapsedSec() const {return std::chrono::duration_cast<std::chrono::nanoseconds>(now()-mBegin).count() * 0.001 * 0.001 * 0.001;}
private:
    std::chrono::system_clock::time_point mBegin;
};

/* 高速な可変長リスト */
template<typename T,int MaxNum>
class FixedVector{
private:
    using Self = FixedVector<T,MaxNum>;
public:
    void pushBack(const T& value){
        mValues[mNum++] = value;
        ASSERT(mNum<=MaxNum);
    }
    void clear(){mNum=0;}
    int indexOf(const T& t)const{for(int i=0;i<mNum;i++){if(mValues[i]==t){return i;}}return -1;}
    void swapAndPop(const T& t){int idx=indexOf(t);if(idx>=0){mValues[idx]=mValues[mNum-1];mNum--;}else{ASSERT(false);}}
    Self& operator=(const Self& v){
        memcpy(mValues, v.mValues, sizeof(T)*v.mNum);
        mNum=v.mNum;
        return *this;}
    T& operator[](int idx){
        ASSERT(idx>=0);
        ASSERT(idx<mNum);
        return mValues[idx];
    }
    const T& operator[](int idx)const{
        ASSERT(idx>=0);
        ASSERT(idx<mNum);
        return mValues[idx];
    }
    int size()const{return mNum;}
    struct iterator{
        int mIdx=0;
        iterator& operator++(){mIdx++;return *this;}
        const T& operator*(){return mValues[mIdx];}
        bool operator==(const iterator& it)const{return mIdx==it.mIdx;}
        bool operator!=(const iterator& it)const{return !(*this==it);}
        const T* mValues = nullptr;
    };
    
    iterator begin() const{iterator it;it.mIdx=0;it.mValues=mValues;return it;}
    iterator end() const{iterator it;it.mIdx=mNum;return it;}

private:
    int mNum=0;
    T mValues[MaxNum];
};

Discussion