// Independent numerical certificates for IBM Ponder This, July 2026.
// Build: c++ -O3 -std=c++17 scripts/research/verify-superheroes.cpp -o /tmp/verify-superheroes
// Run: /tmp/verify-superheroes > public/data/superheroes-certificates.json
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
struct Puzzle {
 int n,p,stamp=0; vector<int> seen,weight,match;
 Puzzle(int N,int P):n(N),p(P),seen(P),weight(N*N),match(N,-1){
  for(int a=1;a<=n;a++)for(int b=1;b<=n;b++){
   ++stamp; int x=0,length=0;
   while(seen[x]!=stamp){seen[x]=stamp;++length;x=(1LL*x*x+1LL*a*x+b)%p;}
   weight[(a-1)*n+b-1]=length;
  }
 }
 int w(int a,int b){return weight[a*n+b];}
 bool augment(int a,int size,int threshold,vector<bool>& visited,bool stronger){
  for(int b=0;b<size;b++)if(!visited[b]&&w(a,b)>=threshold&&(!stronger||a==401||w(a,b)>=350)){
   visited[b]=true;
   if(match[b]<0||augment(match[b],size,threshold,visited,stronger)){match[b]=a;return true;}
  }
  return false;
 }
 bool solve(int size,int t,bool stronger=false){
  fill(match.begin(),match.end(),-1);
  for(int a=0;a<size;a++){vector<bool>v(size);if(!augment(a,size,t,v,stronger))return false;}return true;
 }
 vector<int> permutation(int size){vector<int> r(size);for(int b=0;b<size;b++){assert(match[b]>=0);r[match[b]]=b+1;}return r;}
 int rowmax(int a,int size){int r=0;for(int b=0;b<size;b++)r=max(r,w(a-1,b));return r;}
 int colmax(int b,int size){int r=0;for(int a=0;a<size;a++)r=max(r,w(a,b-1));return r;}
};
void emitArray(const vector<int>&v){cout<<'[';for(size_t i=0;i<v.size();i++){if(i)cout<<',';cout<<v[i];}cout<<']';}
int main(){
 Puzzle main(611,14411);
 // The prime in the supplied PDF is checked against the official puzzle.
 assert(main.colmax(493,611)==349);assert(main.w(401,492)==349);
 assert(main.solve(611,349,true));auto mainperm=main.permutation(611);assert(mainperm[401]==493);
 assert(!main.solve(611,350));
 cerr<<"Required problem: verified optimum 349 and stronger matching.\n";
 Puzzle bonus(999,17377);
 assert(bonus.colmax(1,490)==404);assert(bonus.rowmax(145,777)==405);
 assert(bonus.rowmax(759,999)==408);assert(bonus.colmax(513,923)==405);
 assert(bonus.solve(924,408));auto base=bonus.permutation(924);
 cout<<"{\"method\":\"Direct modular orbit traversal and augmenting-path matching; all indices are one-based.\",\"main\":{\"n\":611,\"p\":14411,\"optimum\":349,\"permutation\":";emitArray(mainperm);
 cout<<"},\"bonus\":{\"p\":17377,\"optimum\":408,\"firstOptimalN\":924,\"basePermutation\":";emitArray(base);cout<<",\"extensions\":[";
 for(int size=925;size<=999;size++){
  vector<bool>vis(size);assert(bonus.augment(size-1,size,408,vis,false));auto next=bonus.permutation(size);
  if(size>925)cout<<',';cout<<"{\"n\":"<<size<<",\"changes\":[";bool first=true;
  for(int a=0;a<size;a++)if(a>=int(base.size())||next[a]!=base[a]){if(!first)cout<<',';first=false;cout<<'['<<a+1<<','<<next[a]<<']';}
  cout<<"]}";base=next;
  vector<bool>used(size);for(int a=0;a<size;a++){assert(!used[base[a]-1]);used[base[a]-1]=true;assert(bonus.w(a,base[a]-1)>=408);}
 }
 cout<<"]},\"upperBounds\":[{\"side\":\"villain\",\"vertex\":493,\"n\":611,\"p\":14411,\"maximum\":349},{\"side\":\"villain\",\"vertex\":1,\"n\":490,\"p\":17377,\"maximum\":404},{\"side\":\"hero\",\"vertex\":145,\"n\":777,\"p\":17377,\"maximum\":405},{\"side\":\"hero\",\"vertex\":759,\"n\":999,\"p\":17377,\"maximum\":408},{\"side\":\"villain\",\"vertex\":513,\"n\":923,\"p\":17377,\"maximum\":405}]}\n";
 cerr<<"Bonus: verified bounds, matching at 924, and extensions through 999.\n";
}