From 12a40a84ddf165f8839dd911839829404070e1cb Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Mon, 1 May 2017 21:26:35 +0200 Subject: Add files via upload --- steadfast_snakes.cpp | 215 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 215 insertions(+) create mode 100644 steadfast_snakes.cpp (limited to 'steadfast_snakes.cpp') diff --git a/steadfast_snakes.cpp b/steadfast_snakes.cpp new file mode 100644 index 0000000..51e3d1e --- /dev/null +++ b/steadfast_snakes.cpp @@ -0,0 +1,215 @@ +// Hacker Cup 2017 +// Round 3 +// Steadfast Snakes +// Jacob Plachta + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +#define LL long long +#define LD long double +#define PR pair + +#define Fox(i,n) for (i=0; i=0; i--) +#define FoxR1(i,n) for (i=n; i>0; i--) +#define FoxRI(i,a,b) for (i=b; i>=a; i--) +#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++) +#define Min(a,b) a=min(a,b) +#define Max(a,b) a=max(a,b) +#define Sz(s) int((s).size()) +#define All(s) (s).begin(),(s).end() +#define Fill(s,v) memset(s,v,sizeof(s)) +#define pb push_back +#define mp make_pair +#define x first +#define y second + +template T Abs(T x) { return(x<0 ? -x : x); } +template T Sqr(T x) { return(x*x); } + +const int INF = (int)1e9; +const LD EPS = 1e-9; +const LD PI = acos(-1.0); + +bool Read(int &x) +{ + char c,r=0,n=0; + x=0; + for(;;) + { + c=getchar(); + if ((c<0) && (!r)) + return(0); + if ((c=='-') && (!r)) + n=1; + else + if ((c>='0') && (c<='9')) + x=x*10+c-'0',r=1; + else + if (r) + break; + } + if (n) + x=-x; + return(1); +} + +#define LIM 800008 + +int L[2]; +LL BLT[2][2][LIM]; + +void Update(int a,int b,int i,int v) +{ + for(i++;i<=L[a];i+=(i&-i)) + BLT[a][b][i]+=v; +} + +LL Query(int a,int b,int i) +{ + LL v=0; + for(i++;i>0;i-=(i&-i)) + v+=BLT[a][b][i]; + return(v); +} + +int main() +{ + // vars + int T,t; + int N,A,B,C; + LL K; + int i,j,c,v,ans; + int r1,r2,m; + LL s; + static int H[LIM]; + static int n1,n2,c1[LIM],c2[LIM],v1[LIM],v2[LIM],vc1[LIM],vc2[LIM]; + // testcase loop + Read(T); + Fox1(t,T) + { + // input + scanf("%d%lld",&N,&K); + Read(v),Read(A),Read(B),Read(C); + Fox(i,N) + { + H[i]=v; + v=((LL)A*v+B)%C+1; + } + // check if there's a single dominating ladder + j=0; + Fox(i,N) + if (H[i]>H[j]) + j=i; + Fox(i,N) + if ((i!=j) && (H[i]>H[j]-K-abs(i-j))) + break; + if (i==N) + { + // special case - only shorten the dominating ladder + ans=0; + Fox(i,N) + if (i!=j) + Max(ans,H[j]-(int)K+H[i]+abs(i-j)); + goto Done; + } + // compress diagonal coordinates + n1=n2=0; + Fox(i,N) + { + c1[n1++]=v1[i]=i-H[i]; + c2[n2++]=v2[i]=-i-H[i]; + } + sort(c1,c1+n1); + sort(c2,c2+n2); + L[0]=n1=unique(c1,c1+n1)-c1; + L[1]=n2=unique(c2,c2+n2)-c2; + Fox(i,N) + { + vc1[i]=lower_bound(c1,c1+n1,v1[i])-c1; + vc2[i]=lower_bound(c2,c2+n2,v2[i])-c2; + } + // init BLTs + Fill(BLT,0); + Fox(i,N) + { + Update(1,0,vc2[i],1); + Update(1,1,vc2[i],v2[i]); + } + // try every possible pyramid center x-coordinate + ans=2*INF+N; + Fox(i,N) + { + // move ladder i from right to left BLT + Update(0,0,vc1[i],1); + Update(0,1,vc1[i],v1[i]); + Update(1,0,vc2[i],-1); + Update(1,1,vc2[i],-v2[i]); + // centered on i + r1=max(i+1,N-i),r2=INF+N; + while (r2>=r1) + { + m=(r1+r2)>>1; + // left + v=i-m; + c=lower_bound(c1,c1+n1,v)-c1-1; + s=Query(0,0,c)*v-Query(0,1,c); + // right + v=-i-m; + c=lower_bound(c2,c2+n2,v)-c2-1; + s+=Query(1,0,c)*v-Query(1,1,c); + if (s<=K) + r2=m-1,Min(ans,2*m); + else + r1=m+1; + } + // centered on i+0.5 + if (i==N-1) + break; + r1=max(i+1,N-i-1),r2=INF+N; + while (r2>=r1) + { + m=(r1+r2)>>1; + // left + v=i-m; + c=lower_bound(c1,c1+n1,v)-c1-1; + s=Query(0,0,c)*v-Query(0,1,c); + // right + v=-(i+1)-m; + c=lower_bound(c2,c2+n2,v)-c2-1; + s+=Query(1,0,c)*v-Query(1,1,c); + if (s<=K) + r2=m-1,Min(ans,2*m+1); + else + r1=m+1; + } + } +Done:; + printf("Case #%d: %d\n",t,ans); + } + return(0); +} -- cgit v1.2.3-18-g5258