bottles2

#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cmath>
#include <random>
#include <utility>
#include <vector>
#include <functional>

using namespace std;

const int N = 1000;
typedef bool Rat[N];
typedef pair<int,int> P;

const double p = 1-sqrt(0.5);
void draw(Rat rat) {
    static random_device rd;
    static mt19937 gen(rd());
    static bernoulli_distribution d(p);
    for (int n=0;n<N;n++) rat[n] = d(gen);
}

bool drink(Rat rat, P p) {
    return rat[p.first] || rat[p.second];
}

P pairs[N*(N-1)/2];
vector<pair<P*,P*>> sets;

long count_remaining() {
    long ret=0;
    for (auto& s : sets) ret+=(s.second-s.first)*((s.second-s.first)-1)/2;
    return ret;
}

long count_solved(Rat rat) {
    auto drinker = bind(drink,rat,placeholders::_1);
    long ret=0;
    for (auto& s : sets) {
        long c=count_if(s.first,s.second,drinker);
        ret+=c*((s.second-s.first)-c);
    }
    return ret;
}

void split(Rat rat) {
    auto drinker = bind(drink,rat,placeholders::_1);
    vector<pair<P*,P*>> newSets;
    for (auto& s : sets) {
        P* mid = partition(s.first,s.second,drinker);
        if (mid-s.first>1) newSets.push_back({s.first,mid});
        if (s.second-mid>1) newSets.push_back({mid,s.second});
    }
    sets = newSets;
}

Rat rats[100];

void init(int K=0) {
    for (int t=0,i=0;i<N;i++) for (int j=0;j<i;j++) pairs[t++]=P{i,j};
    sets.push_back({pairs,end(pairs)});

    for (int k=0;k<K;k++) split(rats[k]);
}

int init_rats() { //some hand-written rats
    for (int k=0,pow3=1;k<7;k++,pow3*=3) {
        for (int n=0;n<N;n++) rats[k][n]=(n/pow3)%3==0;
    }
    for (int k=7,pow3=1;k<14;k++,pow3*=3) {
        for (int n=0;n<N;n++) rats[k][n]=(n/pow3)%3==1;
    }
    for (int k=14,pow3=1;k<20;k++,pow3*=3) {
        for (int n=0;n<N;n++) rats[k][n]=(n/pow3)%3==2;
    }
    return 20;
}

void print(int K) {
    for (int k=0;k<K;k++) {
        for (int n=0;n<N;n++) cout<<(rats[k][n]?1:0);
        cout<<endl;
    }
}

int main() {
    int k=init_rats();
    init(k);
    long rem;
    for (;(rem=count_remaining());k++) {
        cout<<"looking for rat "<<k+1<<" with "<<rem<<" problems"<<endl;
        long max=0;
        Rat rat;
        for (int i=0;i<1000;i++) {
            draw(rat);
            long s = count_solved(rat);
            if (s>max) {
                max=s;
                for (int n=0;n<N;n++) rats[k][n]=rat[n];
            }
        }
        cout<<"found a rat that can solve "<<max<<endl;
        split(rats[k]);
    }
    print(k);
    return 0;
}