HackerEarth Rolling Balls problem solution YASH PAL, 31 July 2024 In this HackerEarth Rolling Balls problem solution There is a segment of length L – 1 meters, and there are L positions on it, numbered 1,2,…,L, equally spaced by 1 meter apart each, in the given order. There are n balls on it, at positions s1,s2,…,sn (si < si+1). Each ball is either rolling to the left of to the right at the speed of 1 meter/second. Whenever two balls hit each other, both of them change direction instantly but keep the same speed. A ball also changes direction when it reaches one of the ends of the segment (position 1 or L). You are given q queries, each one gives you two numbers ti and pi, and you should output the position of the pi-th ball after ti second. HackerEarth Rolling Balls problem solution. #include <bits/stdc++.h>using namespace std;#define x first#define y second#define dbg(x) cout << #x << '=' << x << 'n';#define ll long long#define pi pair<int,int>#define pl pair<ll,ll>#define pd pair<double,double>#define ld long double#define pld pair<ld,ld>#define lg length()#define sz size()#define pb push_back#define MAXN 100005#define INF 1000000005#define LINF 1000000000000000005#define x1 xdddddddddddddddddd#define y1 yddddddddddddddddddint n,q;ll l,s[100005],d[100005],t,p,x[500005],y[500005],g[100005],w[100005],dx[500005],dy[500005];ll md(ll x){ if(x==0) return l; else return x;}int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cin >> l >> n >> q; for(int i=1;i<=n;i++){ cin >> s[i]; } for(int i=1;i<=n;i++){ cin >> d[i]; } int f=1; for(int i=1;i<=n;i++){ if(d[i]){ x[f++]=s[i]; } } for(int i=n;i>=1;i--){ if(!d[i]){ x[f++]=2ll*(l-1)-s[i]; } } for(int i=1;i<=n;i++){ if(d[i]){ x[f++]=2ll*(l-1)+s[i]-2; } } for(int i=n;i>=1;i--){ if(!d[i]){ x[f++]=4ll*(l-1)-s[i]-2; } } for(int i=1;i<=n;i++){ if(d[i]){ w[i]=f; x[f++]=4ll*(l-1)+s[i]-4; } } ll szx=f-1; for(int i=1;i<=szx;i++){ dx[i]=((x[i]-4*(l-1)+4)%l+l)%l; } f=1; for(int i=1;i<=n;i++){ if(!d[i]){ w[i]=f; y[f++]=4ll*(l-1)+s[i]-4; } } for(int i=n;i>=1;i--){ if(d[i]){ y[f++]=6ll*(l-1)-s[i]-4; } } for(int i=1;i<=n;i++){ if(!d[i]){ y[f++]=6ll*(l-1)+s[i]-6; } } for(int i=n;i>=1;i--){ if(d[i]){ y[f++]=8ll*(l-1)-s[i]-6; } } for(int i=1;i<=n;i++){ if(!d[i]){ y[f++]=8ll*(l-1)+s[i]-8; } } ll szy=f-1; for(int i=1;i<=szy;i++){ dy[i]=((y[i]-4*(l-1)+4)%l+l)%l; } f=1; for(int i=1;i<=n;i++){ if(d[i]){ while(y[f]<x[w[i]]) f++; g[i]=f; } } f=szx; for(int i=n;i>=1;i--){ if(!d[i]){ while(x[f]>y[w[i]]) f--; g[i]=f; } } for(int i=1;i<=q;i++){ cin >> t >> p; t%=(2*l-2); ll u=w[p],v=g[p]; if(d[p]){ if(y[v]-x[u]>2*t){ cout << md((dx[u]+t)%l) << 'n'; continue; } ll lt=0,rt=2*n; while(lt!=rt){ ll mt=(lt+rt+1)/2; ll xt=u-(mt+1)/2,yt=v+mt/2; if((y[yt]-x[xt])<=2*t) lt=mt; else rt=mt-1; } ll xt=u-(6+1)/2,yt=v+6/2; if(lt%2==0){ ll nod=v+lt/2; cout << md((dy[nod]-t+2*l)%l) << 'n'; } else{ ll nod=u-(lt+1)/2; cout << md((dx[nod]+t)%l) << 'n'; } } else{ if(y[u]-x[v]>2*t){ cout << md((dy[u]-t+2*l)%l) << 'n'; continue; } ll lt=0,rt=2*n; while(lt!=rt){ ll mt=(lt+rt+1)/2; ll xt=u+(mt+1)/2,yt=v-mt/2; if((y[xt]-x[yt])<=2*t) lt=mt; else rt=mt-1; } if(lt%2==0){ ll nod=v-lt/2; cout << md((dx[nod]+t)%l) << 'n'; } else{ ll nod=u+(lt+1)/2; cout << md((dy[nod]-t+2*l)%l) << 'n'; } } }} Second solution #include <cstdio>#include <cstring>#include <cstdlib>#include <cassert>#include <queue>#include <vector>#include <algorithm>using namespace std;const int MAXN = 100000;const long long INF = 1000000000;vector<long long> left, right;int s[MAXN], d[MAXN];int getCount(const vector<long long>& a, long long l, long long r){ return upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);}bool contains(const vector<long long>& a, long long x){ int index = lower_bound(a.begin(), a.end(), x) - a.begin(); return index < a.size() && a[index] == x;}int check(long long mid, long long t){ int cntRight = getCount(right, 1 - t, mid - t); int cntLeft = getCount(left, 1 + t, mid + t); return cntLeft + cntRight + (contains(right, 0 - t) || contains(left, 0 + t));}int main(){ int n, L, q; assert(scanf("%d%d%d", &L, &n, &q) == 3); assert(1 <= n && n <= MAXN); assert(1 <= q && q <= MAXN); assert(1 <= L && L <= INF); for (int i = 0; i < n; ++ i) { assert(scanf("%d", &s[i]) == 1); fprintf(stderr, "s[i] == %dn", s[i]); assert(1 <= s[i] && s[i] <= L); if (i) { assert(s[i] > s[i - 1]); } } -- L; for (int i = 0; i < n; ++ i) { -- s[i]; assert(0 <= s[i] && s[i] <= L); } for (int i = 0; i < n; ++ i) { assert(scanf("%d", &d[i]) == 1); assert(0 <= d[i] && d[i] <= 1); if (d[i] == 0) { left.push_back(s[i]); right.push_back(0 - s[i]); left.push_back(-2LL * L + s[i]); right.push_back(-2LL * L - s[i]); right.push_back(2LL * L - s[i]); left.push_back(2LL * L + s[i]); } else { right.push_back(s[i]); left.push_back(0 - s[i]); right.push_back(-2LL * L + s[i]); left.push_back(-2LL * L - s[i]); left.push_back(2LL * L - s[i]); right.push_back(2LL * L + s[i]); } } sort(left.begin(), left.end()); sort(right.begin(), right.end()); bool enable_check = ((long long)q * L * n <= 10000000); enable_check = false; while (q --) { int t, p; assert(scanf("%d%d", &t, &p) == 2); assert(1 <= t && t <= INF); assert(1 <= p && p <= n); t %= 2 * L; int l = -1, r = L; while (l + 1 < r) { int mid = (l + r) / 2; if (check(mid, t) >= p) { r = mid; } else { l = mid; } } printf("%dn", r + 1); if (enable_check) { vector<int> tmp, tmpd; for (int i = 0; i < n; ++ i) { tmp.push_back(s[i]); tmpd.push_back(d[i]); } for (int _ = 0; _ < t; ++ _) { for (int i = 0; i < n; ++ i) { if (tmpd[i]) { ++ tmp[i]; } else { -- tmp[i]; } } for (int i = 0; i + 1 < n; ++ i) { if (tmp[i] >= tmp[i + 1]) { swap(tmp[i], tmp[i + 1]); swap(tmpd[i], tmpd[i + 1]); } } if (tmp[0] < 0) { tmp[0] = 1; tmpd[0] ^= 1; } if (tmp.back() > L) { tmp.back() = L - 1; tmpd.back() ^= 1; } } fprintf(stderr, "bruteforce = %d, %dn", tmp[p - 1], p); assert(tmp[p - 1] == r); } } return 0;} coding problems