# HackerEarth Rolling Balls problem solution

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] == %d\n", 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("%d\n", 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, %d\n", tmp[p - 1], p);            assert(tmp[p - 1] == r);        }    }    return 0;}`