I also upsolved it using the same logic.
Hey can anyone help me, and check what’s wrong my code, I’m getting wrong ans
for _ in range(int(input())):
n,m = map(int, input().split())
trains=[int(x) for x in input().split()]
passengers =[int(x) for x in input().split()]
shortest_route=[0]*n
index = -1;
for i in range(n):
if(trains[i] == 1):
index = i
if(index == -1):
shortest_route[i] = -1
continue
shortest_route[i] = i-index
# print(shortest_route)
index = -1;
for i in range(n-1, -1, -1):
if(trains[i] == 2):
index = i
if(index == -1):
continue
shortest_route[i] = min(shortest_route[i], index - i)
# print(shortes_route)
for i in passengers:
if(i == 1):
print(0, end=" ")
continue;
print(shortest_route[i-1], end=" ")
print();Consider the test input:
1
4 5
2 0 2 2
3 4 4 3 4
1 Like
Yeah your guess is correct
If gen.py is a simple test case generator where
Python gen.py N
generates a file with n test cases
Then
for this code
Code
#include<bits/stdc++.h>
#define ll long long
#define PB push_back
using namespace std;
#define MOD 1000000007
ll lev[100005]; //Min Time taken to reach the destination
vector<ll> r,l; //Left and Right trains position
void solve()
{
ll i,n,m;
cin>>n>>m;
//Resetting variables
memset(lev,-1,sizeof(lev));
lev[1]=0;
return ;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
auto begin = std::chrono::high_resolution_clock::now();
ll t=1;
cin>>t;
while(t--)
{
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
return 0;
}
The Respective time taken are as follows
and hence the TLE
3 Likes
Thank You. Now it is giving AC after only assigning -1 to first (n+1) lev elements.
2 Likes
Thank you.
2 Likes
Haha! I got banned for asking how to take fast input. So sorry for this late reply.
This is my solution: CodeChef: Practical coding for everyone. Go to line 70 to skip the template part of it. I believe this is O(n) but this is still getting TLE. Any idea why?
#include<bits/stdc++.h>
#include<string.h>
#include <unordered_map>
#define int long long
#define w(x) int x; cin>>x; while(x–)
int mod=(int)(1e9+7);
#define maxv 2147483647
#define minv -2147483648
#define add push_back
#define MAX (int)1e7+7
using namespace std;
int GCD(int a, int b)
{
if (a % b == 0)
{
return b;
}
return (b, b % a);
}
void sieve()
{
int prime[10000000];
memset(prime, 1, sizeof(prime));
for (int i = 2; i * i <= MAX; i++)
{
if (prime[i])
{
for (int j = i * i; j < MAX; j += i)
{
prime[j] = 0;
}
}
}
for (int i = 3; i <= MAX; i++)
{
prime[i] += prime[i - 1];
}
}
// solve is for seive
/* void solve()
{
int n;
cin >> n;
int ans = prime[n] - prime[n / 2] + 1;
cout << ans << endl;
} */
// pow1 a power b
int mod_mul(int a, int b, int m) {
return (a % m * b % m + m) % m;
}
int pow1(int a, int b, int m) {
int res = 1;
while (b > 0) {
if (b & 1)
{
res = mod_mul(res, a, m);
}
a = mod_mul(a, a, m);
b >>= 1;
}
return res;
}
int max3(int a, int b, int c)
{
if (a >= b && a >= c)
{
return a;
}
if (b >= a && b >= c)
{
return b;
}
return c;
}
int min3(int a, int b, int c)
{
if (a <= b && a <= c)
{
return a;
}
if (b <= a && b <= c)
{
return b;
}
return c;
}
int maxar(int ar[], int n)
{
int k = ar[0];
for (int i = 1; i < n; i++)
{
if (k < ar[i])
{
k = ar[i];
}
}
return k;
}
int minar(int ar[],int n)
{
int k=ar[0];
for(int i=1;i<n;i++)
{
if(ar[i]<k)
{
k=ar[i];
}
}
return k;
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
void yes()
{
cout << “Yes\n”;
}
void no()
{
cout << “No\n”;
}
void factor(int n, int k)
{
vector P;
while (n % 2 == 0)
{
P.push_back(2);
n = n / 2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i + 2)
{
while (n % i == 0)
{
n = n / i;
P.push_back(i);
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2) {
P.push_back(n);
}
if (P.size() < k) {
printf("-1");
return;
}
for (int i = 0; i < k - 1; i++) {
printf("%d ", P[i]);
}
}
void printmat(vector<vector >&G, int n, int m)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << G[i][j] << " ";
} cout << “\n”;
}
}
/*
int bs(int a[],int low,int high,int ans,int key)
{
if(low<=high)
{
int mid=(low+high)/2;
if(a[mid]<=key)
{
return bs(a,mid+1,high,ans,key);
}
else
{
}
}
} */
void pre()
{
}
void solve()
{
int n,k;
int maxi=(1e12+7);
cin>>n>>k;
int a[n],b[k],c[n];
for(int i=0;i<n;i++)
{
c[i]=maxi;
}
int z=-1,fl=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]!=1&&fl==0)
{
c[i]=min(maxi,c[i]);
}
else if(a[i]==1)
{
z=0;
fl=1;
c[i]=min(z,c[i]);
z++;
}
else if(fl==1)
{
c[i]=min(z,c[i]);
z++;
}
}
z=0,fl=0;
/* for(int i=0;i<n;i++)
{
cout<<c[i]<<" “;
}cout<<”\n"; /
for(int i=n-1;i>=0;i–)
{
if(fl==0&&a[i]!=2)
{
c[i]=min(maxi,c[i]);
}
else if(a[i]==2)
{
z=0;
fl=1;
c[i]=min(z,c[i]);
z++;
}
else if(fl==1)
{
c[i]=min(z,c[i]);
z++;
}
}
/ for(int i=0;i<n;i++)
{
cout<<c[i]<<" “;
}cout<<”\n"; */
for(int i=0;i<k;i++)
{
cin>>b[i];
if(b[i]==1)
{
cout<<“0 “;
}
else if(c[b[i]-1]==maxi)
{
cout<<”-1 “;
}
else
{
cout<<c[b[i]-1]<<” “;
}
}cout<<”\n”;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“Input.txt”, “r”, stdin);
freopen(“Output.txt”, “w”, stdout);
#endif
pre();
int t;
cin>>t;
for(int i=0;i<t;i++)
{
solve();
}
}
THIS IS USING PRECOMPUTATION IN C++
https://www.codechef.com/viewsolution/64259656
Help!!! can’t figure out where my solution fails.
Thanks in advance for help