Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <algorithm>
- # include <iostream>
- # include <cstring>
- # include <vector>
- # include <cstdio>
- # include <queue>
- # define long long long // :-)
- using namespace std;
- long const lots=10000000;
- template<class Pred> struct rmq;
- /*.. snip "lrmq.hh" ..*/
- /*.. snip "rsort.hh" ..*/
- typedef pair<long,long> pill;
- struct trill{
- long a,b,c;
- trill(long x=0,long y=0,long z=0):a(x),b(y),c(z){}
- bool operator<(trill const o)const{
- return a<o.a or a==o.a and (b<o.b or b==o.b and c<o.c);
- }
- };
- typedef vector<pill> vpill;
- typedef vector<trill> vtrill;
- rmq<less <long>>** lo_q;
- rmq<greater<long>>** hi_q;
- long* orbit[3];
- long* space;
- long* assoc;
- long *pvp,*wvp;
- long pc,wc;
- int main(){
- pvp=new long[lots*3+4];
- wvp=new long[lots*3+4];
- for (int i=3; i--;) orbit[i]=new long[lots+200];
- space=new long[lots+200];
- assoc=new long[lots*2+200];
- lo_q=new rmq<less <long>> * [lots];
- hi_q=new rmq<greater<long>> * [lots];
- int testcase=1;
- int tsts; scanf("%d",&tsts); while (tsts--){
- long* pv=pvp+lots; // price value
- long* wv=wvp+lots; // weight value
- /* number of elements,
- first price,
- first weight,
- price mod,
- weight mod,
- price multiple,
- price add,
- weight multiple,
- weight add */
- long n, p1,w1, pod,wod, pm,pa, wm,wa;
- cin>>n>>p1>>w1>>pod>>wod>>pm>>pa>>wm>>wa;
- vector<trill> dn,up;
- // generate the sequence cycles
- pv[0]=p1; wv[0]=w1;
- pc=0,wc=0;
- {
- // might need up to n*2 elements at first (>M+1 and >K+1 never happen)
- int* lap=new int[pod+1]; for (long i=pod+1; i--;) lap[i]=0; lap[p1]=1;
- int* law=new int[wod+1]; for (long i=wod+1; i--;) law[i]=0; law[w1]=1;
- while (++pc<n*2) {pv[pc]=((pv[pc-1]*pm+pa)%pod)+1; if (lap[pv[pc]]) break; else lap[pv[pc]]=pc+1;}
- while (++wc<n*2) {wv[wc]=((wv[wc-1]*wm+wa)%wod)+1; if (law[wv[wc]]) break; else law[wv[wc]]=wc+1;}
- // calculate duplication count
- long pdup=lap[pv[pc]]-1;
- long wdup=law[wv[wc]]-1;
- if (pdup==pc+1) pdup=0; pdup=max(min(pdup,n-1),0ll);
- if (wdup==wc+1) wdup=0; wdup=max(min(wdup,n-1),0ll);
- // it's easier to know that length(pv) is not greater than length(wv)
- if (wc-wdup<pc-pdup){
- swap(wc,pc);
- swap(wv,pv);
- swap(pdup,wdup);
- }
- // unique elements are a special case
- for (long i=max(pdup,wdup); i--;)
- dn.push_back(trill(wv[i%wc],pv[i%pc],1)),
- up.push_back(trill(wv[i%wc],pv[i%pc],1)),
- --n;
- pv+=pdup, pc-=pdup;
- wv+=wdup, wc-=wdup;
- pc=min((long)pc,n);
- wc=min((long)wc,n);
- while (wdup>pdup and wdup--){
- ++pv, pv[pc-1]=pv[-1];
- }
- while (pdup>wdup and pdup--){
- ++wv, wv[wc-1]=wv[-1];
- }
- delete[] lap; delete[] law;
- }
- // the drift per generation is the reference list length mod the basis list length
- long drift=wc%pc;
- // build orbits
- int orbits=0, spaces=0;
- {
- bool* done=new bool[pc];
- for (int i=pc; i--;) done[i]=false;
- for (int i=0; i<pc; i++)
- if (not done[i]){
- orbit[2][orbits ]=i;
- orbit[0][orbits ]=spaces;
- for (int j=i; !done[j]; j=fastmod(j+drift,pc))
- done[j]=true, space[spaces]=pv[j], assoc[j*2]=orbits, assoc[j*2+1]=spaces++;
- orbit[1][orbits++]=spaces;
- }
- delete[] done;
- }
- // construct range minimum query tables
- for (int i=orbits; i--;)
- lo_q[i]=new rmq< less<long>>(space+orbit[0][i],space+orbit[1][i]),
- hi_q[i]=new rmq<greater<long>>(space+orbit[0][i],space+orbit[1][i]);
- // find and count outliers
- for (long i=0; i<wc; i++){
- long id=i%pc;
- long count=(n-i+wc-1)/wc;
- ulong off=orbit[0][assoc[id*2]];
- long l=assoc[id*2+1]-off;
- long r=l+count;
- long period=(orbit[1][assoc[id*2]]-orbit[0][assoc[id*2]])*wc;
- long loop=orbit[1][assoc[id*2]]-orbit[0][assoc[id*2]];
- long u=lo_q[assoc[id*2]]->query(l,r); dn.push_back(trill(wv[i],space[u+off],(count-((loop+u-l)%loop)+loop-1)/loop));
- long v=hi_q[assoc[id*2]]->query(l,r); up.push_back(trill(wv[i],space[v+off],(count-((loop+v-l)%loop)+loop-1)/loop));
- }
- for (int i=orbits; i--;)
- delete lo_q[i], delete hi_[i];
- rad_sort(dn.begin(),dn.end());
- rad_sort(up.begin(),up.end());
- long red=0,rep=0;
- long sad=(1ll<<40ll),sap=-(1ll<<40ll);
- for (long i=0; i<dn.size(); i++){
- //if (dn[i].b<sad) printf("%lld: %lld * %lld\n",dn[i].a,dn[i].b,dn[i].c);
- if (dn[i].b<sad)
- sad=dn[i].b,
- red+=dn[i].c;
- }
- for (long i=up.size(); i--;){
- //if (up[i].b>sap) printf("%lld: %lld * %lld\n",up[i].a,up[i].b,up[i].c);
- if (up[i].b>sap)
- sap=up[i].b,
- rep+=up[i].c;
- }
- printf("Case #%d: %lld %lld\n",testcase++,rep,red);
- }
- for (long i=3; i--;) delete[] orbit[i];
- delete[] space;
- delete[] assoc;
- delete[] pvp;
- delete[] wvp;
- delete[] lo_q;
- delete[] hi_q;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement