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] == %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;
}
0 Comments