12356 - Army Buddies
Moderator: Board moderators
12356 - Army Buddies
Since I coded in C++, I got TL when I used cout statements for this problem. However, when I switched to printf, I got AC. (Note that I was already using scanf to read data in (instead of cin).)
Update: Input / output removed after it was pointed out to be faulty. Thanks brianfry713 and mhsn06.
Update: Input / output removed after it was pointed out to be faulty. Thanks brianfry713 and mhsn06.
Last edited by uDebug on Thu Sep 04, 2014 7:15 am, edited 2 times in total.
Re: 12356 - Army Buddies
1 <= L <=R <= N
what is the meaning of L>R input?
3 2
They are already killed. how it could be?
2 3
what is the meaning of L>R input?
3 2
They are already killed. how it could be?
2 3
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
v1n1t, your input is invalid.
Check input and AC output for thousands of problems on uDebug!
Re: 12356 - Army Buddies
Thanks for bringing this to my attention. I've removed my input.brianfry713 wrote:v1n1t, your input is invalid.
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 12356 - Army Buddies
I am getting TLE with my code. Please suggest me any faster way.
Code: Select all
#include<stdio.h>
int main()
{
int n,r,L,R,p[100003],i,j,l,fL,fR,rp,lm,rm;
while(scanf("%d %d",&n,&rp)!=EOF)
{
for(i=1;i<=n;i++)
p[i]=1; /* initially all soldiers are alive */
if(n==0 && rp==0)
break;
for(i=1;i<=rp;i++)
{
fL=fR=0; //Assume left and right buddies are dead and not exist
scanf("%d %d",&L,&R);
for(j=L;j<=R;j++) //from L to R all buddies are killed
p[j]=0;
if(L>1)
{
for(j=L-1;j>=1;j--) // search alive left buddy from L-1 to 1
{
if(p[j]>0)
{
l=j;
fL=1; // as a left alive buddy found
break;
}
}
}
if(R<n)
{
for(j=R+1;j<=n;j++) // search alive right buddy from R+1 to n
{
if(p[j]>0)
{
r=j;
fR=1; // as a right alive buddy found
break;
}
}
}
if(fL==0) // if left buddy not exist
printf("* ");
else
printf("%d ",l);
if(fR==0) // if right buddy not exist
printf("*\n");
else
printf("%d\n",r);
}
printf("-\n");
}
return 0;
}
Last edited by Shahidul.CSE on Sat Sep 13, 2014 1:34 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
Don't read from a file.
Check input and AC output for thousands of problems on uDebug!
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 12356 - Army Buddies
Actually I submitted my code not using freopen(...);brianfry713 wrote:Don't read from a file.
I just used it for checking input and output.
But my code getting TLE
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
You can answer each query in constant time.
At the start of each test case initialize two int arrays that keep track each of the S soldiers nearest living neighbor to the left and right.
For each of the B loss reports print the neighbor values from the arrays, and update (also in constant time) the left and right arrays of the new neighbors.
Total running time should be O(S + B) for each test case, your code runs in O(S * B).
At the start of each test case initialize two int arrays that keep track each of the S soldiers nearest living neighbor to the left and right.
For each of the B loss reports print the neighbor values from the arrays, and update (also in constant time) the left and right arrays of the new neighbors.
Total running time should be O(S + B) for each test case, your code runs in O(S * B).
Check input and AC output for thousands of problems on uDebug!
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 12356 - Army Buddies
Code: Select all
Accepted !
Last edited by Shahidul.CSE on Tue Sep 16, 2014 8:19 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
Code: Select all
foreach 1 <= i <= S
left[i] = i - 1 and right[i] = i + 1
foreach of the B loss reports
print left[L], right[R]
left[right[R]] = left[L]
right[left[L]] = right[R]
Check input and AC output for thousands of problems on uDebug!
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 12356 - Army Buddies
Code: Select all
Accepted !
Last edited by Shahidul.CSE on Tue Sep 16, 2014 8:17 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!
-
- Experienced poster
- Posts: 148
- Joined: Sun Jul 13, 2014 4:32 am
- Location: Rangpur, Bangladesh
Re: 12356 - Army Buddies
To
brianfry713,
Thanks sir, got ACCEPTED![:D](./images/smilies/icon_biggrin.gif)
brianfry713,
Thanks sir, got ACCEPTED
![:D](./images/smilies/icon_biggrin.gif)
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Re: 12356 - Army Buddies
Hello,
I/O functions should be a factor in here?
I have an AC solution in C++ which runs in 0.175 seconds if I use printf and scanf, but goes TLE if I use cin and cout.
What do you guys think about that?
I/O functions should be a factor in here?
I have an AC solution in C++ which runs in 0.175 seconds if I use printf and scanf, but goes TLE if I use cin and cout.
What do you guys think about that?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12356 - Army Buddies
Yes printf and scanf are faster than cin and cout.
Check input and AC output for thousands of problems on uDebug!