Can someone help me find mistake ,I am getting WA
I traversed array left to right for station 1 an then right to left for station 2 to get a minimum distance array named result for each station
time complexity O(n)
#include<iostream>
using namespace std;
int main(void) {
int t;
cin>>t;
while(t--)
{
int cities;
int people;
cin>>cities;
cin>>people;
int a[cities];
int b[people];
int result[cities];
for(int i=0;i<cities;i++)
{
cin>>a[i];
}
for(int i=0;i<people;i++)
{
int destination;
cin>>destination;
b[i]=destination-1;
}
for(int i=0;i<cities;i++)
result[i]=1000000009;
int pos=-1;
for(int i=0;i<cities;i++)
{
if(a[i]==1)
{
pos=i;
}
if(pos!=-1)
{
if(a[i]==2)
result[i]=0;
else
result[i]=min(result[i],i-pos);
}
}
int pos2=-1;
for(int i=cities;i>=0;i--)
{
if(a[i]==2)
{
pos2=i;
}
if(pos2!=-1)
{
if(a[i]==1)
result[i]=0;
else
result[i]=min(result[i],pos2-i);
}
}
for(int i=0;i<people;i++)
{
if(result[b[i]]!=1000000009)
cout<<result[b[i]]<<" ";
else
cout<<-1<<" ";
}
cout<<endl;
}
}
let say if the test case is like this.
6 1
1 2 0 1 2 0
3
now,
I used two multimaps to keep track of stations.
1st map for train numbered 1 and second map for train numbered 2.
so for above test case maps would look like this.
map 1 :
index | train number
1 | 1 (train with number 1 at index 1)
4 | 1 (train with number 1 at index 4)
map 2:
index | train Number
2 | 2
5 | 2
I have ignored the station 0/
now for every query I just need to find the lower_bound of the query
as here q = 3
so I have to find the lower_bound of 3 in map one and the same for map 2
now I have to display the min( (q - lower_bound(3).map1 ) , ( lower_bound(3).map2 - q ) )
/*
TLE
written by Aashray Bavisa
on 14 June 2021
*/
#include <iostream>
#include <cstdlib>
#define MARS \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define endl '\n'
using namespace std;
#define S ' '
#define pfor(iter, init, lim, diff) for (int iter = init; iter < lim; iter += diff)
void solve()
{
int stations, travellers;
cin >> stations >> travellers;
int train[stations];
pfor(i, 0, stations, 1)
{
cin >> train[i];
}
pfor(i, 0, travellers, 1)
{
int t;
cin >> t;
// decreased by one just to count from 0
t--;
// if desired station has train at time = 0
if (train[t])
cout << 0;
else
{
int c = 1;
bool f = 1;
while (t - c >= 0 || t + c < stations)
{
// if left side stations have train going in right side i.e. == 1
// or right side stations have traing going in left side i.e. = 2
// whenever we got first occurance of that, we got our minimum station
if ((t - c >= 0 && train[t - c] == 1) || (t + c < stations && train[t + c] == 2))
{
cout << c;
f = 0;
break;
}
c++;
}
// if couldn't find any station satisfying our condition
if (f)
cout << -1;
}
cout << S;
}
cout << endl;
}
int main()
{
MARS;
int TC = 1;
cin >> TC;
for (int u = 1; u <= TC; u++)
solve();
return 0;
}
