summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--broken_bits.cpp167
-rw-r--r--pie_packages.cpp240
-rw-r--r--sluggish_security.cpp203
-rw-r--r--steadfast_snakes.cpp215
4 files changed, 0 insertions, 825 deletions
diff --git a/broken_bits.cpp b/broken_bits.cpp
deleted file mode 100644
index de08d4d..0000000
--- a/broken_bits.cpp
+++ /dev/null
@@ -1,167 +0,0 @@
-// Hacker Cup 2017
-// Round 3
-// Broken Bits
-// Jacob Plachta
-
-#include <algorithm>
-#include <functional>
-#include <numeric>
-#include <iostream>
-#include <iomanip>
-#include <cstdio>
-#include <cmath>
-#include <complex>
-#include <cstdlib>
-#include <ctime>
-#include <cstring>
-#include <cassert>
-#include <string>
-#include <vector>
-#include <list>
-#include <map>
-#include <set>
-#include <deque>
-#include <queue>
-#include <stack>
-#include <bitset>
-#include <sstream>
-using namespace std;
-
-#define LL long long
-#define LD long double
-#define PR pair<int,int>
-
-#define Fox(i,n) for (i=0; i<n; i++)
-#define Fox1(i,n) for (i=1; i<=n; i++)
-#define FoxI(i,a,b) for (i=a; i<=b; i++)
-#define FoxR(i,n) for (i=(n)-1; 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<typename T> T Abs(T x) { return(x<0 ? -x : x); }
-template<typename T> 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);
-}
-
-int main()
-{
- // vars
- int T,t;
- int N,K;
- int i,a,b,ones,origOnes,forceZero;
- bool allOnes;
- LL v1,v2,ans;
- int origL[60],L[60];
- // testcase loop
- Read(T);
- Fox1(t,T)
- {
- // input
- Read(N),Read(K);
- ones=0;
- Fox(i,N)
- Read(L[i]),ones+=L[i];
- origOnes=ones=K-ones;
- memcpy(origL,L,sizeof(L));
- // all unknowns must be 0 or 1?
- if ((!ones) || (N==K))
- {
- ans=0;
- goto Done;
- }
- // 2 leading 0s (can never differentiate them)?
- if (L[0]+L[1]==0)
- {
- ans=-1;
- goto Done;
- }
- // try all possible key 0 sequences
- ans=0;
- Fox1(a,N-1)
- if ((!origL[a]) && (origL[a-1]))
- Fox(forceZero,2)
- {
- // find end of key 0 sequence
- memcpy(L,origL,sizeof(L));
- ones=origOnes;
- FoxI(i,a,N-1)
- if (L[i])
- break;
- b=i-1;
- // allocate as many 1s on the left of the key sequence as possible
- // (but leaving at least 1, and optionally forcing one of them to be 0)
- allOnes=1;
- Fox(i,a)
- if (!L[i])
- if ((ones>1) && ((!allOnes) || (!forceZero)))
- L[i]=1,ones--;
- else
- allOnes=0;
- // allocate as many 1s as close to the end as possible (but leaving at least 1)
- FoxRI(i,b+1,N-1)
- if ((!L[i]) && (ones>1))
- L[i]=1,ones--;
- // in key sequence, use smallest possible allocation
- if (!ones)
- continue;
- FoxRI(i,a,b)
- if (ones)
- L[i]=1,ones--;
- if (ones)
- continue;
- // if left of key sequence is all 1s, use 2nd-smallest allocation instead
- if (allOnes)
- if (!next_permutation(L+a,L+b+1))
- continue;
- v1=0;
- Fox(i,N)
- v1=v1*2+L[i];
- // state will be known once key sequence wraps around
- FoxI(i,a,N-1)
- L[i]=1;
- v2=0;
- Fox(i,N)
- v2=v2*2+L[i];
- Max(ans,v2-v1+1);
- }
- // output
-Done:;
- printf("Case #%d: %lld\n",t,ans);
- }
- return(0);
-} \ No newline at end of file
diff --git a/pie_packages.cpp b/pie_packages.cpp
deleted file mode 100644
index 1224328..0000000
--- a/pie_packages.cpp
+++ /dev/null
@@ -1,240 +0,0 @@
-// Hacker Cup 2017
-// Round 3
-// Pie Packages
-// Jacob Plachta
-
-#include <algorithm>
-#include <functional>
-#include <numeric>
-#include <iostream>
-#include <iomanip>
-#include <cstdio>
-#include <cmath>
-#include <complex>
-#include <cstdlib>
-#include <ctime>
-#include <cstring>
-#include <cassert>
-#include <string>
-#include <vector>
-#include <list>
-#include <map>
-#include <set>
-#include <deque>
-#include <queue>
-#include <stack>
-#include <bitset>
-#include <sstream>
-using namespace std;
-
-#define LL long long
-#define LD long double
-#define PR pair<int,int>
-
-#define Fox(i,n) for (i=0; i<n; i++)
-#define Fox1(i,n) for (i=1; i<=n; i++)
-#define FoxI(i,a,b) for (i=a; i<=b; i++)
-#define FoxR(i,n) for (i=(n)-1; 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<typename T> T Abs(T x) { return(x<0 ? -x : x); }
-template<typename T> 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 2000001
-#define MOD 1000000007
-#define DIV2 500000004
-
-int Add(int a,int b)
-{
- a+=b;
- if (a>=MOD)
- a-=MOD;
- return(a);
-}
-
-int Sub(int a,int b)
-{
- a-=b;
- if (a<0)
- a+=MOD;
- return(a);
-}
-
-int Mult(int a,int b)
-{
- return((LL)a*b%MOD);
-}
-
-int main()
-{
- // vars
- int T,t;
- int N;
- int O,Ao,Bo,Co,Do;
- int C,Ac,Bc,Cc,Dc;
- int i,j,k,d,d2,ans;
- int r1,r2,m;
- LL a,b,c;
- static int E[LIM],dist[LIM],sum[LIM];
- static LL D1[LIM],D2[LIM],S1[LIM],S2[LIM];
- static vector<PR> con[LIM];
- priority_queue<PR> Q;
- // testcase loop
- Read(T);
- Fox1(t,T)
- {
- // input
- Read(N);
- Fox(i,N+1)
- con[i].clear();
- Read(O),Read(Ao),Read(Bo),Read(Co),Read(Do);
- Fox(i,N)
- {
- E[i]=O;
- j=(i+1)%N;
- con[i].pb(mp(j,O));
- con[j].pb(mp(i,O));
- O=((LL)Ao*O+Bo)%Co+Do;
- }
- Read(C),Read(Ac),Read(Bc),Read(Cc),Read(Dc);
- Fox(i,N)
- {
- con[N].pb(mp(i,C));
- con[i].pb(mp(N,C));
- C=((LL)Ac*C+Bc)%Cc+Dc;
- }
- // precompute outer distances/sums
- D1[0]=D2[0]=S1[0]=S2[0]=0;
- Fox(i,N*2)
- {
- D1[i+1]=D1[i]+E[i%N];
- D2[i+1]=D2[i]+E[(N*2-i-1)%N];
- S1[i+1]=Add(S1[i],D1[i+1]%MOD);
- S2[i+1]=Add(S2[i],D2[i+1]%MOD);
- }
- // dijkstra's from center
- Fill(dist,60);
- Q.push(mp(0,N)),dist[N]=0;
- while (!Q.empty())
- {
- d=-Q.top().x;
- i=Q.top().y;
- Q.pop();
- if (d!=dist[i])
- continue;
- Fox(j,Sz(con[i]))
- {
- k=con[i][j].x;
- d2=d+con[i][j].y;
- if (d2<dist[k])
- Q.push(mp(-d2,k)),dist[k]=d2;
- }
- }
- // precompute center distance sums
- sum[0]=0;
- Fox(i,N*2)
- sum[i+1]=Add(sum[i],dist[i%N]);
- // process outer points
- j=ans=0;
- Fox(i,N)
- {
- // advance j to furthest node from i (along outside only)
- for(;;)
- {
- c=D1[j]-D1[i];
- a=min(c,D1[N]-c);
- c=D1[j+1]-D1[i];
- b=min(c,D1[N]-c);
- if (b<=a)
- break;
- j++;
- }
- // binary search for furthest node in i..j which is closer along the ouside
- r1=i,r2=j;
- while (r2>r1)
- {
- m=(r1+r2+1)>>1;
- if (D1[m]-D1[i]<dist[i]+dist[m%N])
- r1=m;
- else
- r2=m-1;
- }
- a=r1;
- // binary search for furthest node in j..(i+N) which is closer along the ouside
- r1=j,r2=i+N;
- while (r2>r1)
- {
- m=(r1+r2)>>1;
- if (D1[i+N]-D1[m]<dist[i]+dist[m%N])
- r2=m;
- else
- r1=m+1;
- }
- b=r1;
- if (a==b)
- {
- c=D1[a]-D1[i];
- if (c<D1[N]-c)
- b++;
- else
- a--;
- }
- // add outer distances i -> i..a
- ans=Add(ans,Sub(S1[a],S1[i]));
- ans=Sub(ans,Mult(D1[i]%MOD,a-i));
- // add outer distances i -> b..(i+N)
- ans=Add(ans,Sub(S2[N*2-b],S2[N*2-(i+N)]));
- ans=Sub(ans,Mult(D2[N*2-(i+N)]%MOD,i+N-b));
- // add distances through center i -> (a+1)..(b-1)
- if (a+1<=b-1)
- {
- ans=Add(ans,Mult(dist[i],b-a-1));
- ans=Add(ans,Sub(sum[b],sum[a+1]));
- }
- }
- // add center distances
- ans=Mult(ans,DIV2);
- ans=Add(ans,sum[N]);
- // output
- printf("Case #%d: %d\n",t,ans);
- }
- return(0);
-} \ No newline at end of file
diff --git a/sluggish_security.cpp b/sluggish_security.cpp
deleted file mode 100644
index 33f30b0..0000000
--- a/sluggish_security.cpp
+++ /dev/null
@@ -1,203 +0,0 @@
-// Hacker Cup 2017
-// Round 3
-// Sluggish Security
-// Jacob Plachta
-
-#include <algorithm>
-#include <functional>
-#include <numeric>
-#include <iostream>
-#include <iomanip>
-#include <cstdio>
-#include <cmath>
-#include <complex>
-#include <cstdlib>
-#include <ctime>
-#include <cstring>
-#include <cassert>
-#include <string>
-#include <vector>
-#include <list>
-#include <map>
-#include <set>
-#include <deque>
-#include <queue>
-#include <stack>
-#include <bitset>
-#include <sstream>
-using namespace std;
-
-#define LL long long
-#define LD long double
-#define PR pair<int,int>
-
-#define Fox(i,n) for (i=0; i<n; i++)
-#define Fox1(i,n) for (i=1; i<=n; i++)
-#define FoxI(i,a,b) for (i=a; i<=b; i++)
-#define FoxR(i,n) for (i=(n)-1; 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<typename T> T Abs(T x) { return(x<0 ? -x : x); }
-template<typename T> 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 2000005
-#define MOD 1000000007
-
-int A[LIM],B[LIM],S[LIM];
-LL fct[LIM],ifct[LIM];
-
-PR gcd(int a,int b)
-{
- if (!b)
- return(mp(1,0));
- PR p=gcd(b,a%b);
- return(mp(p.y,p.x-p.y*(a/b)));
-}
-
-int Ch(int n,int k)
-{
- return(fct[n]*ifct[k]%MOD*ifct[n-k]%MOD);
-}
-
-int main()
-{
- // vars
- int T,t;
- int N,Ka,Kb;
- int i,j,a,b;
- int ans;
- // precompute factorials and their modular inverses
- Fox(i,LIM)
- {
- fct[i]=i ? fct[i-1]*i%MOD : 1;
- ifct[i]=gcd(fct[i],MOD).x;
- if (ifct[i]<0)
- ifct[i]+=MOD;
- }
- // testcase loop
- Read(T);
- Fox1(t,T)
- {
- // input
- Read(N);
- Read(A[0]),Read(Ka),N=1;
- while (Ka--)
- {
- Read(a),Read(b);
- Fox(i,b)
- Read(S[i]);
- while (a--)
- Fox(i,b) {
- A[N]=A[N-1]+S[i];
- N++;
- }
- }
- Read(B[0]),Read(Kb),N=1;
- while (Kb--)
- {
- Read(a),Read(b);
- Fox(i,b)
- Read(S[i]);
- while (a--)
- Fox(i,b) {
- B[N]=B[N-1]+S[i];
- N++;
- }
- }
- // pad arrays
- a=-1;
- Fox(j,4)
- {
- A[N+j]=a--;
- B[N+j]=a--;
- }
- // iterate through
- ans=1;
- i=j=a=b=0;
- while ((i<N) || (j<N))
- if (
- (A[i]==B[j]) ||
- (A[i]==B[j+1]) && (A[i+1]==B[j]) ||
- (A[i]==A[i+2]) && (A[i+1]==B[j]) ||
- (B[j]==B[j+2]) && (B[j+1]==A[i])
- ) {
- // cross pattern, must end current streaks
- ans=(LL)ans*Ch(a+b,a)%MOD;
- a=b=0;
- if (A[i]==B[j])
- i++,j++;
- else
- {
- ans=(ans<<1)%MOD;
- if (A[i]==A[i+2])
- i+=3,j++;
- else
- if (B[j]==B[j+2])
- j+=3,i++;
- else
- i+=2,j+=2;
- }
- }
- else
- // continue one of the current streaks?
- if (A[i]==A[i+1])
- i+=2,a++;
- else
- if (B[j]==B[j+1])
- j+=2,b++;
- else
- if ((A[i]==A[i+2]) && (A[i+1]==A[i+3]))
- i+=4,a++;
- else
- if ((B[j]==B[j+2]) && (B[j+1]==B[j+3]))
- j+=4,b++;
- else
- {
- // impossible pattern
- ans=0;
- break;
- }
- ans=(LL)ans*Ch(a+b,a)%MOD;
- // output
- printf("Case #%d: %d\n",t,ans);
- }
- return(0);
-} \ No newline at end of file
diff --git a/steadfast_snakes.cpp b/steadfast_snakes.cpp
deleted file mode 100644
index 51e3d1e..0000000
--- a/steadfast_snakes.cpp
+++ /dev/null
@@ -1,215 +0,0 @@
-// Hacker Cup 2017
-// Round 3
-// Steadfast Snakes
-// Jacob Plachta
-
-#include <algorithm>
-#include <functional>
-#include <numeric>
-#include <iostream>
-#include <iomanip>
-#include <cstdio>
-#include <cmath>
-#include <complex>
-#include <cstdlib>
-#include <ctime>
-#include <cstring>
-#include <cassert>
-#include <string>
-#include <vector>
-#include <list>
-#include <map>
-#include <set>
-#include <deque>
-#include <queue>
-#include <stack>
-#include <bitset>
-#include <sstream>
-using namespace std;
-
-#define LL long long
-#define LD long double
-#define PR pair<int,int>
-
-#define Fox(i,n) for (i=0; i<n; i++)
-#define Fox1(i,n) for (i=1; i<=n; i++)
-#define FoxI(i,a,b) for (i=a; i<=b; i++)
-#define FoxR(i,n) for (i=(n)-1; 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<typename T> T Abs(T x) { return(x<0 ? -x : x); }
-template<typename T> 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);
-}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-22 02:21:31 +0000