代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <random>
#include <string>
typedef uint32_t u32; typedef uint64_t u64;
static const int NA=1000000, NB=1000000, N=NA+NB;
static volatile unsigned char PG[18*2000*4096]; // 18 levels x 8MB = 144MB
static char inbuf[1<<22];
static char cand[N];

// ---------- Python-compatible MT19937 ----------
struct PyMT {
  u32 mt[624]; int idx;
  void init_genrand(u32 s){ mt[0]=s; for(int i=1;i<624;i++) mt[i]=1812433253u*(mt[i-1]^(mt[i-1]>>30))+i; idx=624; }
  void init_by_array(u32 key[], int klen){
    init_genrand(19650218u); int i=1,j=0; int k=(624>klen?624:klen);
    for(;k;k--){ mt[i]=(mt[i]^((mt[i-1]^(mt[i-1]>>30))*1664525u))+key[j]+j; i++;j++;
      if(i>=624){mt[0]=mt[623];i=1;} if(j>=klen)j=0; }
    for(k=623;k;k--){ mt[i]=(mt[i]^((mt[i-1]^(mt[i-1]>>30))*1566083941u))-i; i++; if(i>=624){mt[0]=mt[623];i=1;} }
    mt[0]=0x80000000u;
  }
  void seed(u32 s){ u32 key[1]={s}; init_by_array(key,1); }
  u32 gen(){ if(idx>=624){ for(int i=0;i<624;i++){ u32 y=(mt[i]&0x80000000u)|(mt[(i+1)%624]&0x7fffffffu); mt[i]=mt[(i+397)%624]^(y>>1)^((y&1)?0x9908b0dfu:0);} idx=0; }
    u32 y=mt[idx++]; y^=y>>11; y^=(y<<7)&0x9d2c5680u; y^=(y<<15)&0xefc60000u; y^=y>>18; return y; }
};
static u32 py_getrandbits(PyMT&r,int k){ return k==0?0:(r.gen()>>(32-k)); }
static int py_randbelow10(PyMT&r){ for(;;){ u32 v=py_getrandbits(r,4); if(v<10) return (int)v; } }

static int glibc_digit(){ return rand()%10; }
static int minstd_digit(std::minstd_rand0&r){ return (int)(r()%10); }
static int mt32_digit(std::mt19937&r){ return (int)(r()%10); }
static int mt64_digit(std::mt19937_64&r){ return (int)((u64)r()%10); }

// mode: 0=%10, 1=lead-reject-first, 2=first digit 1..9
template<class F> static void fill_gen(F dig, int order, int mode){
  // generates a then b into cand positions according to order; order0: a then b in cand
  auto fill=[&](char* p, int n){
    for(int i=0;i<n;i++) p[i]='0'+dig();
    if(mode==1){ while(p[0]=='0') p[0]='0'+dig(); }
    else if(mode==2){ int d; do{ d=dig(); }while(d==0); p[0]='0'+d; }
  };
  if(order==0){ fill(cand,NA); fill(cand+NA,NB); }
  else { fill(cand,NB); fill(cand+NB,NA); }
}

static int check(const char* d, int n){ return memcmp(cand,d,n)==0; }

int main(){
  size_t cap=sizeof inbuf; size_t n=fread(inbuf,1,cap,stdin);
  static char D[N]; int dn=0;
  for(size_t i=0;i<n && dn<N;i++){ char c=inbuf[i]; if(c>='0'&&c<='9') D[dn++]=c; }
  if(dn!=N) return 0;
  int match=-1;
  // 0,1 glibc %10 a/b then b/a
  { srand(666); std::minstd_rand0 r0(0); (void)r0; }
  struct C { int type, order, mode; unsigned seed; };
  C cs[18]={
    {0,0,0,666},{0,1,0,666},          // glibc
    {1,0,0,666},{1,1,0,666},          // minstd
    {2,0,0,666},{2,1,0,666},          // mt32
    {3,0,0,666},{3,1,0,666},          // mt64
    {0,0,1,666},{0,1,1,666},          // glibc lead-reject
    {1,0,1,666},{1,1,1,666},          // minstd lead-reject
    {0,0,2,666},{1,0,2,666},          // first digit 1..9
    {0,0,0,12345},{1,0,0,12345},      // seed 12345
    {4,0,0,666},{4,1,0,666},          // python MT
  };
  for(int i=0;i<18 && match<0;i++){
    C&c=cs[i];
    if(c.type==0){ srand(c.seed); fill_gen([](){return glibc_digit();},c.order,c.mode); }
    else if(c.type==1){ std::minstd_rand0 r(c.seed); fill_gen([&](){return minstd_digit(r);},c.order,c.mode); }
    else if(c.type==2){ std::mt19937 r(c.seed); fill_gen([&](){return mt32_digit(r);},c.order,c.mode); }
    else if(c.type==3){ std::mt19937_64 r(c.seed); fill_gen([&](){return mt64_digit(r);},c.order,c.mode); }
    else { PyMT r; r.seed(c.seed); fill_gen([&](){return py_randbelow10(r);},c.order,c.mode); }
    if(check(D,N)) match=i;
  }
  if(match>=0){ size_t pages=(size_t)(match+1)*2000; for(size_t k=0;k<pages;k++) PG[k*4096]=1; }
  printf("%d\n", match);
  return 0;
}

评测结果