I tried coding up the solution using “upper_bound” and “lower_bound” as well but it seems it doesn’t work for me. If the editorialist can clear this out as to why it doesn’t work for me it will be great.
#include <map>
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
void printVector(vector<int> vec) {
cout << "printing vector : " << endl;
for (int i = 0; i < vec.size(); ++i) {
cout << vec[i] << " ";
}
cout << endl;
}
void solve() {
int N, M;
scanf("%d", &N);
scanf("%d", &M);
vector<int> Ai(N + 1, 0);
vector<int> Bi(M + 1, 0);
vector<int> Ci(M+1, 0);
vector<int> rightTrains;
vector<int> leftTrains;
for (int i = 1; i <= N; ++i) {
scanf("%d", &Ai[i]);
if (Ai[i] == 1) {
rightTrains.push_back(i);
}
if (Ai[i] == 2) {
leftTrains.push_back(i);
}
}
for (int i = 1; i <= M; ++i) {
scanf("%d", &Bi[i]);
}
// sort the vectors for the trains going to the right and the left
sort(rightTrains.begin(), rightTrains.end());
sort(leftTrains.begin(), leftTrains.end());
//printVector(rightTrains);
// printVector(leftTrains);
for (int i = 1; i <= M; ++i) {
// if the destination of the traveller is the first station itself
// then they are already there and hence time taken is 0
if (Bi[i] == 1) {
Ci[i] = 0;
continue;
}
// in the case when every station has 0 trains and the destination
// is not 1
if (rightTrains.size() == 0 && leftTrains.size() == 0) {
Ci[i] = -1;
continue;
}
int lb, ub;
lb = ub = -1;
if (rightTrains.size() != 0) {
auto lowerBound = lower_bound(rightTrains.begin(), rightTrains.end(), Bi[i]);
cout << "lowerBound index : " << lowerBound - rightTrains.begin() << endl;
lb = rightTrains[lowerBound - rightTrains.begin()];
}
if (leftTrains.size() != 0) {
auto upperBound = upper_bound(leftTrains.begin(), leftTrains.end(), Bi[i]);
cout << "upperBound index : " << upperBound - leftTrains.begin() << endl;
ub = leftTrains[upperBound - leftTrains.begin()];
}
cout << "lb : " << lb << " ub : " << ub << endl;
if (lb != -1 && ub == -1) {
Ci[i] = abs(lb - Bi[i]);
continue;
}
if (lb == -1 && ub != -1) {
Ci[i] = abs(ub - Bi[i]);
continue;
}
Ci[i] = min(abs(lb - Bi[i]), abs(ub - Bi[i]));
}
for (int i = 1; i <= M-1; ++i) {
printf("%d ", Ci[i]);
}
printf("%d\n", Ci[M]);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
}
Can you guys make a review on my solution. I merged both left and right train directions in a common vector like in a Dijsktra algorithm but it didn’t work for me. I’m not sure if it was an I/O issue because I ran many sample tests and it always gave me the correct answer. Thanks for your help. Here is my solution in C++:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int T;
scanf("%d\n", &T);
for (int i = 0; i < T; i++)
{
int N, M;
scanf("%d %d\n", &N, &M);
vector<int> dist(N, INT_MAX);
dist[0] = 0;
// Building the distance vector
for (int i = 0; i < N; i++)
{
int direction;
scanf("%d", &direction);
if ((direction == 1)) {
dist[i] = 0;
int j = 1;
while ((i + j < N) && (dist[i + j] > j)) dist[i + j] = j, j++;
}
else if (direction == 2) {
dist[i] = 0;
int j = 1;
while ((i - j >= 0) && (dist[i - j] > j)) dist[i - j] = j, j++;
}
}
for (int i = 0; i < M; i++)
{
int destiny;
scanf("%d", &destiny);
printf("%d ", (dist[destiny - 1] != INT_MAX)? dist[destiny - 1] : -1);
}
printf("\n");
}
return 0;
}
Hi can anyone help me find what is wrong with my solution?
It’s almost similar to Editorials solution, but I got Wrong Answer
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include <bits/stdc++.h>
using namespace std;
long long int best[100002];
long long int A[100002];
long long int B[100002];
int main()
{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
long long int T;
cin>>T;
while (T--)
{
long long int N,M,a,b;
cin>>N>>M;
long long int left = -1,right=N;
for(long long int i=0;i<N;i++)
{
best[i] = -1;
}
for(long long int i=0;i<N;i++)
{
cin>>A[i];
}
for(long long int i=0;i<M;i++)
{
cin>>B[i];
}
for(long long int i=0;i<N;i++)
{
if(A[i] == 1)
left = i;
if(left != -1)
best[i] = i-left;
}
for(long long int i=N-1;i>=0;i--)
{
if(A[i] == 2)
right = i;
if(right != N)
if((best[i] == -1) || (best[i] > (right-i)))
best[i] = right - i;
}
for(long long int i=0;i<M;i++)
{
cout<<best[B[i]-1]<<" ";
}
cout<<"\n";
}
}
abhijeetgupto - if you process the full city set for every query, you will be doing far too much data handling. Much better to separate out the up-train and down-train cities and then use those either to search for suitable journey start points or pre-process to a time map; something like:
ups = []
downs = [0]
for city, dirn in enumerate(trains, start=1):
if dirn == 1:
ups.append(city)
elif dirn == 2:
downs.append(city)
However: if you hadn’t gotten TLE, you would have gotten WA. The results from a single test case are supposed to be delivered on a single line of space-separated values.
Fast output is as important as fast input in this case - you need to limit your print statements.
