enumeration of antimatroid, bforce + symmetries + parallel

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <mutex>
#include <thread>

using namespace std;

typedef unsigned long long ull;
typedef unsigned int us;


int n = 7;
const int N = 1<<n;
const ull all = -1;
const int thread_cnt = 8;

const int factorial[] = {1,1,2,6,24,120,720,5040};


class u128
{
    public:
        ull low;
        ull high;
        u128(ull _low=0, ull _high = 0)
        {
            low = _low;
            high = _high;
        }

        bool operator<(const u128& b) const
        {
            return (high==b.high) ? (low<b.low) : (high<b.high);
        }

        bool operator==(const u128& b) const
        {
            return (high==b.high) && (low==b.low);
        }

        u128 operator~() const
        {
            return u128(~low,~high);
        }

        u128 operator&(const u128& b) const
        {
            return u128(low&b.low, high&b.high);
        }

        u128 operator|=(const u128& b)
        {
            low |= b.low;
            high |= b.high;
            return *this;
        }
        u128 operator&=(const u128& b)
        {
            low &= b.low;
            high &= b.high;
            return *this;
        }

        void setbit(unsigned i)
        {
            if(i<64)
                low |= (1ull << i);
            else
                high |= (1ull << (i-64));
        }

        void erasebit(unsigned i)
        {
            if(i<64)
                low &= ~(1ull << i);
            else
                high &= ~(1ull << (i-64));
        }

        bool getbit(unsigned i) const
        {
            return (i<64) ? (low & (1ull << i)) : (high & (1ull << (i-64)));
        }

        void scan()
        {
            cin >> low >> high;
        }

        void print() const
        {
            cout << low << ' ' << high << endl;
        }

};

const int magic = 2000003;
int hash_(const u128& X)
{
    int ret = (X.low%magic)+(X.high%magic);
    return ret<magic?ret:ret-magic;
}
class hashtable
{
    public:
        vector<vector<u128> > table;
        int size;
        mutex mtx_;
        hashtable()
        {
            table.resize(magic);
            size = 0;
        }
        void insert(const u128& X)
        {
            int h = hash_(X);
            bool ok = true;
            mtx_.lock();
            for(auto& i : table[h])
                if(i==X)
                {
                    ok = false;
                    break;
                }
            if(ok)
            {
                table[h].push_back(X);
                size++;
            }
            mtx_.unlock();
        }
};

class producer
{
    mutex mtx_;
    public:
    int s;
    bool get(u128& x)
    {
        lock_guard<mutex> guard(mtx_);
        if(s==0)
            return false;
        s--;
        x.scan();
        return true;
    }
};

vector<vector<int> > perms;
int psize;
vector<vector<int> > ap;
vector<u128> pred;
vector<u128> succ;

int apply(vector<int> p, int x)
{
    int y = 0;
    for(int i=0;i<n;i++)
        if(x & (1<<i))
            y |= 1<<p[i];
    return y;
}

pair<u128,vector<int> > _reduce(const u128& X)
{
    u128 R;
    vector<int> C = {0};
    vector<int> nC;
    C.reserve(psize);
    nC.reserve(psize);
    R.setbit(0);
    int i=1;
    for(int bit=0;bit<n;bit++)
    {
        int ss = C.size();
        C.resize(ss*(n-bit));
        for(int it=ss;it<ss*(n-bit);it++)
            C[it] = C[it-ss]+factorial[n-1-bit];
        for(;i<(1<<(bit+1));i++)
        {
            nC.clear();
            bool v = false;
            for(auto& t : C)
            {
                bool nv = X.getbit(ap[i][t]);
                if(nv > v)
                {
                    nC.clear();
                    v = nv;
                    R.setbit(i);
                }
                if(nv == v)
                {
                    nC.push_back(t);
                }
            }
            swap(nC,C);
        }
    }
    return make_pair(R,C);
}
u128 reduce(const u128& X)
{
    return _reduce(X).first;
}
vector<int> aut(const u128& X)
{
    return _reduce(X).second;
}

producer P;
hashtable nL;

class counter
{
    mutex mtx_;
    public:
        long long cnt;
        void inc(long long x)
        {
            mtx_.lock();
            cnt += x;
            mtx_.unlock();
        }

};

counter ans;

void consumer()
{
    u128 S;
    while(P.get(S))
    {
        vector<int> automorph = aut(S);
        ans.inc(psize/automorph.size());
        u128 mask(0,0);
        for(int I=1;I<N-1;I++)
            if(S.getbit(I))
                for(int J=1;J<I;J++)
                    if(S.getbit(J))
                    {
                        int IJ = I|J;
                        if(IJ != I && IJ != J)
                            mask.setbit(IJ);
                    }


        mask = S & ~mask;
        u128 f1,f2;
        for(int I=0;I<N;I++)
            if(S.getbit(I))
            {
                f2 |= succ[I] & f1;
                f1 |= succ[I];
            }
        f1 &= ~f2 & S;
        for(int I=0;I<N;I++)
            if(f1.getbit(I))
                mask = mask & ~pred[I];

        for(int I=1;I<N-1;I++)
            if(mask.getbit(I))
            {
                for(int a=0;a<automorph.size();a++)
                    mask.erasebit(ap[I][automorph[a]]);
                u128 nS = S;
                nS.erasebit(I);
                nL.insert(reduce(nS));
            }
    }
}


int main()
{
    pred.resize(N);
    succ.resize(N);
    for(int I=0;I<N;I++)
        for(int i=0;i<n;i++)
            if(I & (1<<i))
                pred[I].setbit(I & ~(1<<i));
            else
                succ[I].setbit(I | (1<<i));
    vector<int> start;
    for(int i=0;i<n;i++)
        start.push_back(i);
    do
    {
        perms.push_back(start);
    }
    while(next_permutation(start.begin(),start.end()));
    psize = perms.size();
    ap.resize(N, vector<int>(psize));

    for(int p=0;p<psize;p++)
        for(int i=0;i<N;i++)
            ap[i][p] = apply(perms[p], i);

    int bc = N;
    cin >> bc >> ans.cnt >> P.s;

    cerr << bc << " : " << P.s << endl;
    bc--;

    vector<thread> threads;
    for(int i=0;i<thread_cnt;i++)
      threads.emplace_back(consumer);
    for (auto& t: threads) t.join();

    cerr << bc << " : " << nL.size << endl;
    cout << bc << ' ' << ans.cnt << endl;
    cout << nL.size << endl;
    for(int ii=0;ii<magic;ii++)
        for(auto& it : nL.table[ii])
            it.print();
}