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 ydddddddddddddddddd

int 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